正整数Nの最大の素因数を求めるアルゴリズムがわかりません。
ネットで検索して一応出てきたのですが、どうしても理解できません。

int i,no=N; //Nは正整数
for(i=2;i*i<=no;i++){
while(no%i==0) no/=i;
}

iまたはnoのどちらかに求めたい素因数が入っています。
なぜこれで求めることができるのでしょうか?
noやiが非素数ということもあり得るのでは?

ずっと考えましたがわかりません。
誰か教えてください。

このQ&Aに関連する最新のQ&A

A 回答 (5件)

ANo.4で参考に挙げた知恵袋の質問が消えそうなので


そちらで紹介した代替案を転載します

----
こんな方法ではどうでしょう?

int no = N;
int i, p = 1;
// iは素因数候補, pは各段階での最大素因数
for(i=2;i*i <= no;i++){
if(no % i == 0){
p = i; // より大きい素因数が見つかったので, 最大素因数を更新する
while(no % i == 0) no /= i; // noを素因数候補iで割れるだけ割る
}
}
// no = 3*7のように最大素因数が√noより大きい場合は最後のnoが最大素因数
if(no > p) p = no;

最後にはpにNの最大の素因数が入っていることになります

しくみは以下のとおり
noが素数か1になるまで素因数候補i で小さいものから順に割り続けます
すると素因数候補i が合成数の場合には絶対にnoを割り切れなくなります
ですので
noの最大の素因数は, 素数になったときのnoか最後にnoを割り切った数のどちらかです

あとは, noと最後にnoを割り切った数pを比較して大きい方を選べば
最大の素因数が得られることになります
----
    • good
    • 0

リンク先の質問でも答えたのですが


このアルゴリズムは, iもnoも非素数になる場合があります
Nが素数のべき乗になっている場合です

例えば
N=81 (3の4乗)の場合です
iとnoの値を追いかけてみます

まず
int i,no=81; のように変数に値をセットして, for文の繰り返しを実行します

i=2のとき, 2*2 <= 81なので, forのカッコ内を処理する
81 % 2 != 0なので, whileのカッコ内の処理をしない

i=3のとき, 3*3 <= no (=81)なので, forのカッコ内を処理する
81 % 3 == 0なので, whileのカッコ内の処理(no = 81/3 = 27)をする
27 % 3 == 0なので, 同様にno = 27/3 = 9をする
9 % 3 == 0なので, 同様にno = 9/3 = 3をする
3 % 3 == 0なので, 同様にno = 3/3 = 1をする
1 % 3 != 0なので, whileのカッコ内の処理をしない

i=4のとき, 4*4 > no (=1)なので, forのカッコ内を処理しない
となって, 繰り返しが終了します

このとき
i=4, no=1 ですが, これらは81の最大の素因数ではありません

参考URL:http://detail.chiebukuro.yahoo.co.jp/qa/question …
    • good
    • 0

a<b<cで、c=a*bだとして、i=cになった時点で、noは素因数にaもbも含まない状態になっているので、aとbの積であるcも当然noの素因数には含まれません。


なので、no%i==0の条件を満たすことはなく、no/=iの処理も行われません。
    • good
    • 0

Nが素数なら、2<=i<=√Nの範囲で、whileループ条件であるno%i==0にあてはまるiは存在しないので、no/=iは実行されることがなく、no=Nのまま終了します。



whileループでは、一度no%i==0の条件に当てはまったら、そのiでnoが割り切れなくなるまで繰り返します。
それを、i*i<noの条件を満たす限り、iを大きくしながら繰り返します。

noを割り切れるiがなくなったら、終了。

終了した時点で、noを割り切れるi(素数)がないんだから、noは素数ですよね。

iは2から1ずつ大きくしているから、iが非素数であることはありますが、forループでiがそんな値になったときには、whileループ条件のno%i==0には当てはまらないようになっています。
    • good
    • 0

まず, ちょっと考えれば


・2以上 √N 以下のどの整数でも割り切れないなら N は素数
であることがわかります (N = pq とおくと p と q の一方は √N 以下). また,
・N を割り切る (2以上の) 最小の整数が素数
であることも簡単にわかります (素数でないと仮定して背理法が簡単?).

だから「no や i が非素数」ということはありえません.
    • good
    • 0

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Q「熊猫」?それとも「猫熊」?

お世話になります。
かつて中国語を学習したとき、パンダは「熊猫」だと教えられました。
先日台湾人とパンダの話題(最近中国から譲渡された)になったとき、
「熊猫」だと「熊みたいな猫」だと言われ、「猫熊」が正しいと聞きました。
中国や台湾のウェブサイトを検索しましたが、「熊猫」「猫熊」どちらの表記もみることができます。
中国=「熊猫」  台湾=「猫熊」 と使い分けているのでしょうか?
それとも最近になって「猫熊」と言い直されているのでしょうか?

よろしくお願いします。

Aベストアンサー

百度のこちらと似たサイトに出ている質問に対する回答↓を見ると、
http://zhidao.baidu.com/question/2906297.html
No.3 の方のおっしゃる通りですね。

もともと、学名で「猫熊」だったものが、国共内戦の混乱期以降に「熊猫」と表記されるようになったので、その後の大陸には「熊猫」が広まり、中華民国が言葉を持ち込んだ台湾では本来の「猫熊」が保存されているということでしょう。

新聞記者が博覧会の展示の右から書いた名前を左から読んだためというのが本当であれば、言葉に対するマスコミの威力を感じますし、それでもパンダのいない台湾で「猫熊」が保存されたという点では国民党政府の力を感じます。

Q自然数nを素因数分解すると、素因数は2と3であり、それ以外の素因数はない。また、nの正の約数の個数は

自然数nを素因数分解すると、素因数は2と3であり、それ以外の素因数はない。また、nの正の約数の個数はちょうど12である。このような自然数nをすべて求めよ。
わかる方教えてください!

Aベストアンサー

n=2^a×3^bと表せます。^aはa乗を示します。
abはそれぞれ自然数です。
ここで約数の数は(a+1)×(b+1)=12と表せます。
これは(a=1,b=5)(a=2,b=3)(a=3,b=2)(a=5,b=1)の4通りです。
それぞれnを求めると、486,108,72,96となります。

Q比良山系熊遭遇

ヤマレコで高島トレイルで熊に遭遇し負傷したとありました。
登山口に熊目撃情報が張り出しています。
以前わたしも付近の登山道で目の前約100m位のところで見かけその月終わりにも登山道隅で大きく真新しい糞がありました。
この時期熊は活発なんでしょうか?
いつも熊鈴を付けてはいるのですが効果はあるのでしょうか?

Aベストアンサー

熊鈴はリスク軽減と言う考え方ですね。
1%でも遭遇の可能性が減るなら付ける。
遭遇の可能性が極端に低い山で付けると迷惑がられます。

気付かせる努力と気付く努力と考えるとラジオなど
音の出っぱなしの物は熊の存在に気付くのが遅れ危険です。

熊は人間の存在に気付くと逃げるとは限らず隠れる場合があります。
それを察して熊に気付かないフリをするのも重要なテクニックです。
山に犬を連れて行くなと言うのは、これが理由です。
犬が隠れてる熊を発見してしまうのです・・・
まぁ 極端に遭遇率の高い山での話ですが参考までに。

確率から考えるならば、
登山口までの交通事故の方が何倍も危険です(笑)

Qm^2+n^2=8m-6n を満たす正の整数の組(m,n)をすべて求める

m^2+n^2=8m-6n を満たす正の整数の組(m,n)をすべて求めよ。

また親戚の子供に聞かれて困っています。。

ご教授ください。
宜しくお願いします。

Aベストアンサー

先ほどの解答は間違えました。
0と25の場合も追加しなければなりません。
3)m-4=0、n+3=±5のとき、題意を満たすのは
  m=4、n=2
4)m-4=±5、n+3=0のときは
  n=-3となり、不適。

よって先ほどの解答は間違いで、
(m,n)=(1,1)、(7,1)、(4,2) 
となります。
すみません。

Q「熊」のアクセントは前?後?

最近、各地で「熊」が出没して被害が出ているようですね。ところで、この「熊」のアクセントは、「くま」(↓)(高低)が正しいと思うのですが、テレビのアナウンサーは、NHKでも民法でも、ほぼすべてが、「くま」(↑)(低高)と言います。私が正しいのか、アナウンサーが正しいのか、どちらでしょうか。熊が出たときに困るので、教えてください。

「熊が出た」
「熊による被害」
などの「熊」のアクセントの位置をお教えください。

Aベストアンサー

次の辞書には「2」「1」両方のアクセントが載せられています。
http://dic.yahoo.co.jp/dsearch?enc=UTF-8&p=%E3%81%8F%E3%81%BE&dtype=0&stype=1&dname=0ss&pagenum=1&index=105510000000
本来は「2」 (「橋」の型) でしたが、かなり前から「1」の型が増えてきました。
ですから、
オーソドックスには「2」だが、「1」も認められる。
ということになります。
下に「○○(が)」の場合の高低を図示します。

「2」 _| ̄|(_) 「橋が」の型
http://dic.yahoo.co.jp/dsearch?enc=UTF-8&p=%E6%A9%8B&dtype=0&stype=1&dname=0ss&pagenum=1&index=115656500000
「1」  ̄|_ (_) 「箸が」の型
http://dic.yahoo.co.jp/dsearch?enc=UTF-8&p=%E3%81%AF%E3%81%97&dtype=0&stype=1&dname=0ss&pagenum=1&index=115656400000
「0」 _| ̄ ( ̄) 「端が」の型
http://dic.yahoo.co.jp/dsearch?enc=UTF-8&p=%E3%81%AF%E3%81%97&dtype=0&stype=1&dname=0ss&pagenum=1&index=115656200000

次の辞書には「2」「1」両方のアクセントが載せられています。
http://dic.yahoo.co.jp/dsearch?enc=UTF-8&p=%E3%81%8F%E3%81%BE&dtype=0&stype=1&dname=0ss&pagenum=1&index=105510000000
本来は「2」 (「橋」の型) でしたが、かなり前から「1」の型が増えてきました。
ですから、
オーソドックスには「2」だが、「1」も認められる。
ということになります。
下に「○○(が)」の場合の高低を図示します。

「2」 _| ̄|(_) 「橋が」の型
http://dic.yahoo.co.jp/dsearch?enc=UTF-8&p=%E6%A9%8B&d...続きを読む

Qnを正の整数とする時、6の倍数であることを証明する n(n+1)(n+2) n3乗+5n

nを正の整数とする時、6の倍数であることを証明する n(n+1)(n+2) n3乗+5n

Aベストアンサー

n~3+5n も、n(n+1)(n+2) と同様、
必ず 6 の倍数になります。

簡単なのは、mod 6 で
n~3+5n ≡ n~3+(-1)n ≡ (n-1)n(n+1)
として、前小問に帰着することですが、
これだと、多少、知識が要りますね。

n を 6 で割った商を q、余りを r と置いて、
n = 6q+r を式に代入すると、
n~3+5n を 6 で割った余りが
r~3+5r を 6 で割った余りと一致する
ことが判ります。
あとは、r = 0,1,2,3,4,5 の各々について
余りを求めてみればよい。

Q「なまはげ」の格好で山登りをしたら、熊は逃げますか?

「なまはげ」の格好で山登りをしたら、熊は逃げますか?

今年は夏の猛暑の影響からか、山に熊のえさが不足していて、人と熊が遭遇する機会が増えているようです。

そこで、せめてもの防衛策として「なまはげ」の格好をして山登りをしたら、もし出会っても熊は逃げますか?
出会わないで済みそうだと思いますか?

Aベストアンサー

強さの順で言えば、熊も所詮は人間と同じ哺乳類ですから神の使いで鬼の仲間である、なまはげには敵わないので逃げます。

ただし、これは本物のなまはげであった場合のみの話で、人間とばれたら襲われるでしょう。

「なまはげ」の格好で山登りをして効果があるのは大晦日と2月の数日(だったような^^;)の間だけです。

これ以外の時期では熊が「今の時期になまはげが居るわけ無い」と襲ってきます。

なまはげが熊に通じる時期と本州以南に生息している大多数の熊の冬眠時期が重なることは、自然の摂理とは言え非常に残念なことだと私は常日頃から思っています。



※よい子の皆は信じたり実行したりしないでね。

Q”部分分数分解(m/nのm,nは整数)のアルゴリズム化の方針を示せ。”

”部分分数分解(m/nのm,nは整数)のアルゴリズム化の方針を示せ。”です。
内容は情報ではなく数学なので、ここで質問をさせていただきます。

m/n * x/x = mx/nx

mx/nx = (mx-n)/nx + n/nx = (mx-n)/nx + 1/x
ただし、mx-n>0, mx>n

∴mx/nx = m/nより

m/n = mx/nx = (mx-n)/nx + 1/x , ただし、mx>nとなるxを定める必要がある。
x={n(分母)/m(分子)の小数点以下切り捨て}+1であれば常にmx>nは満たされる。

あとは再帰的にm ← mx-n (次の分子をmx-nに更新), n ← nx (次の分母をnxに更新)
でループ処理をして最新の分子が1の時にブレイクすれば処理完了。

というプログラム化の方針でどうでしょうか?
プログラムの作成より、方向性を示せと言われる方が細部の説明において難しいですね…orz

Aベストアンサー

>ループに入る前に入力された数値のチェックを入れればOKでしょうか?

ループに入る前だけではなく、ループの中でもチェックする必要があります。

例えば、5/6の場合、
5/6 = (5*2-6)/6*2 + 1/2 = 4/12 + 1/2
4/12 = (4*4-12)/12*4 + 1/4 = 4/48 + 1/4
4/48 = (4*13-48)/48*13 + 1/13 = 4/624 + 1/13
これ以上やっても無限ループになります。


m/n = mx/nx = (mx-n)/nx + 1/x
としたあとで、(mx-n)/nxを約分して既約分数にする必要があります。


ただし、上記のチェックだけで本当に無限ループにならないかどうかの数学的な証明は必要です。

Q熊被害について

 最近ニュースなどで熊の出没・被害が多発していると伝えられているところですが,そこで気になってしまったことがあります。

 何故,熊は殺されなければいけないのですか?山に入った人が被害に遭っても,熊は殺されてしまいます。いわば熊の領域に人が勝手に入り込んでいるわけですよね?
 また,山から下りて,人間の生活域に入ってしまった熊も,殺されたりしますね。人間は良くて,熊は悪い。
 
 他方,人を襲う猿は殺されていない。この違いは何でしょうか?単に,直接人間が死の危険にさらされるからだけなんですか?
 
 教えて下さい,熊達の殺されている意味を。 
 また,皆さんのご意見を聞かせて頂ければ幸いです。
 

Aベストアンサー

#1です。

>熊が射殺された話題や,骸の映像などを見ては,今までと同じ事を考えてしまうと思います・・・。

そうした感情を抱かれるのはごく普通の事ですよ。

#1のリンク先の回答にも書いたように
「クマがかわいそう」と感じるのは「人間の勝手な感情」だと考えていますが
そうした感情を抱く事が間違っているだとか
意味のない事だとか言うつもりはまったくありません。

人間が自分の価値観・感情で物事を考えるのは
当然、というよりは必然の事であって
それを否定する事には何の意味もありません。
(「自分の価値観だけで物事を考えるのは良くない」なんても一つの価値観ですしね)

私もペットとして飼っている猫は愛情を注いで可愛がっていますが
その猫のおやつも兼ねているニボシは平気で頭から丸かじりします。
別々の存在と見なしている以上、「生き物」なんて括りで
すべてを同列に考えられるはずはありません。

それがごく普通の事なんですよ。逆に
「命はみんな大切」「すべての生き物は平等」なんて意見の方が
崇高な建前に陶酔しているだけの無意味な考え方だと感じます。

射殺されるクマをかわいそうだと感じるのは
kunai0001さんの優しさなのですから、恥じる事でも否定する事でもありません。

#1です。

>熊が射殺された話題や,骸の映像などを見ては,今までと同じ事を考えてしまうと思います・・・。

そうした感情を抱かれるのはごく普通の事ですよ。

#1のリンク先の回答にも書いたように
「クマがかわいそう」と感じるのは「人間の勝手な感情」だと考えていますが
そうした感情を抱く事が間違っているだとか
意味のない事だとか言うつもりはまったくありません。

人間が自分の価値観・感情で物事を考えるのは
当然、というよりは必然の事であって
それを否定する事には何の意味もありま...続きを読む

Q極限値lim[n→∞](3^n/(2^n+n^2))とlim[n→∞](2^n+3^n)^(1/n)の求め方は?

(1)lim[n→∞](3^n/(2^n+n^2))
(2)lim[n→∞](2^n+3^n)^(1/n)

の極限値がわかりません。
(1)は3^nで分母・分子を割って
lim[n→∞](3^n/(2^n+n^2))
=
lim[n→∞][1/{(2/3)^n+n^2/3^n}]
までいけたのですがn^2/3^nが収束するのか発散するのか分かりません。
どうなるのでしょうか?

あと、(2)は対数を取って
lim[n→∞]log(2^n+3^n)^(1/n)
=
lim[n→∞](1/n)log(2^n+3^n)
までいけたのですがここから先へ進めません。

Aベストアンサー

YYoshikawaさん、こんにちは。

[(1)について]

> n^2/3^nが収束するのか発散するのか分かりません。

まず感覚として、ANo.1さんも書かれているように、n=100で考えてみると、
 n^2/3^n = 10000/3^100
ですが、3^2=9 が大体10ですから、3^100 は、10^50 ぐらいなわけで、0が50個ぐらいつきますから、10000などよりは、はるかに大きくなります。つまり n^2/3^n → 0 が予想できます。

数式では次のように証明できます。

まず、n^2/3^n はnが大きいとき単調減少です。
実際、a(n)=n^2/3^n とおき、

 a(n+1)/a(n) = [(n+1)^2/3^(n+1)]/[n^2/3^n]

と比をとってみると、

 a(n+1)/a(n) = [1+(1/n)]^2/3 = [1 + 2/n + 1/n^2]/3 … (3)

ですが、nが大きいときには、2/n < 1, 1/n^2 < 1 なので、(3)は、

 a(n+1)/a(n) < 1

となり、単調に減少することがわかります。
まずこの時点で発散はしないことがわかります。
また、a(n) > 0 なので、lim_{n→∞} a(n) ≧ 0 となります。

もし、a(n) の収束値bが、正の有限値なら、n→∞で、
 a(2n)/a(n) → b/b = 1
になるはずですが、
 a(2n)/a(n) = [(2n)^2/3^{2n}]/[n^2/3^n] = 4/3^n → 0
になるので、収束値bは正の有限値にはなりません。

従って、
 lim_{n→∞} a(n) = 0 … (4)
が得られます。

[(4)の別証]
(3)式 a(n+1)/a(n) = [1+(1/n)]^2/3 = [1 + 2/n + 1/n^2]/3 より、
n>10で、
 a(n+1)/a(n) < [1 + 2/10 + 1/100]/3 < 2/3
故に、n→∞ のとき、
 0 < a(n) = [a(n)/a(n-1)]・[a(n-1)/a(n-2)] ・…・ [a(12)/a(11)]・a(11)
      < (2/3)^{n-11}× a(11) = (2/3)^n × (3/2)^{11}a(11) → 0
故に
 lim_{n→∞} a(n) = 0
が得られる。
(別証終わり)


[(2)について]

まず感覚的なことを説明しますと、nが大きいとき、2^nは3^nに比べてはるかに小さくなるので、基本的に、lim[n→∞](2^n+3^n)^(1/n)の、2^n+3^nの部分は3^nに近づくことがわかり、問題の式は(3^n)^{1/n}=3 になることが予想されます。

これを式で言うには、対数をとるより、

 lim_{n→∞} [3^n×{1+(2/3)^n}]^{1/n}
 = lim_{n→∞} 3×[1+(2/3)^n]^{1/n} … (5)

と変形するのが良いでしょう。(2/3)^n → 0 なので、
 [1+(2/3)^n]^{1/n} → 1 … (6)
なので、
 (5) = 3
になります。


なお、(6)が明らかと思われない場合は、
 1 = 1^{1/n} < [1+(2/3)^n]^{1/n} < 1+(2/3)^n → 1
(∵ a > 1 に対して、a^{1/n} = (a^{1/n})^n = a )
より、[1+(2/3)^n]^{1/n} → 1
と証明します。

YYoshikawaさん、こんにちは。

[(1)について]

> n^2/3^nが収束するのか発散するのか分かりません。

まず感覚として、ANo.1さんも書かれているように、n=100で考えてみると、
 n^2/3^n = 10000/3^100
ですが、3^2=9 が大体10ですから、3^100 は、10^50 ぐらいなわけで、0が50個ぐらいつきますから、10000などよりは、はるかに大きくなります。つまり n^2/3^n → 0 が予想できます。

数式では次のように証明できます。

まず、n^2/3^n はnが大きいとき単調減少です。
実際、a(n)=n^2/3^n とおき、...続きを読む


人気Q&Aランキング