正整数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が見つからない時は、教えて!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岐阜県のホームセンター

岐阜県のホームセンター

岐阜県で最大の売場面積を持つホームセンターは何処でしょうか?

Aベストアンサー

スーパービバホーム岐阜柳津店
「売場面積11,284平方メートルで岐阜県最大級のホームセンターです。」
http://shop.vivahome.co.jp/user/svh/gifuyanaizu_svh/

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「世界最大の恐竜博」入場前売り券

「世界最大の恐竜博」入場前売り券を、山形県内で扱っておられる場所を教えて下さい。

Aベストアンサー

前売り券は、JR東日本みどりの窓口、びゅうプラザ、近畿日本ツーリスト、JTB、JTBトラベランドなどの主要旅行代理店、チケットぴあ、ローソンチケット、CNプレイガイドなどの主要プレイガイドにて購入できるそうです。

参考URL:http://www.familytb.com/themepark/new.html#1

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最大軸トルクと最大軸出力の発生エンジン回転速度が違う理由を教えてください

エンジンの性能曲線図をみると
最大軸トルクが120N・m/4000min-1に対し、
最大軸出力が65kW/6500min-1
となって、発生エンジン回転速度が違うのですが、

この理由について分かる方がいらっしゃれば、教えていただきたいです。

Aベストアンサー

同じような質問が続いているけど。
トルクQkg・mとパワーPpsとの関係は

P=Q*(2πN)/4500 N;エンジン回転数rpm

単位が古いのは許してね。

完全にフラットなトルク特性(回転力)なら仕事率Pはエンジン回転数が高いほど大きくなります。
しかしトルク特性は図の通り山なりになります。そのためトルクが下がる量と回転数のバランスで最大出力の回転数が決まります。
これでよいかな?

Q2つの整数124,77を自然数nで割ったとき、余りがそれぞれ4,5となる最大の自然数nを求めよ。 解

2つの整数124,77を自然数nで割ったとき、余りがそれぞれ4,5となる最大の自然数nを求めよ。



124-4=120, 77-5=72より、120と72の最大公約数を求める。
120=2×2×2×3 ×5
72=2×2×2×3×3
最大公約数は2×2×2×3=24

答え n=24

意味分かりません!
なぜ120-4,77-5?
なぜ最大公約数を求めたら、問題文の言う、自然数nで割ったとき余りがそれぞれ4、5となる最大の自然数nになるんで?

Aベストアンサー

124をある数(自然数)で割ると4余るということは、120をある数で割れば割り切れるということです。
77も同様に、72だったら割り切れるということ。

それで120と72は同じ数で割り切れるんだから、この二つの数の公約数を探してみると、
120=2×2×2×3×5
72=2×2×2×3×3
このうち一番大きい数は、2×2×2×3=24です。

Q総武線(千葉県)沿線の駅から行けるホームセンター

総武線の千葉(西船橋~千葉間)から、徒歩またはバスで行けるホームセンターを探しています。千葉駅周辺であれば自転車でもよいです。ご存知の方がいましたら、よろしくお願いします。

Aベストアンサー

規模を求めないのならば、東船橋のケイヨーD2(駅から300Mぐらい)
http://www.keiyo.co.jp/map/chiba/images/007higasihunabasi08.02.jpg

なお、ケイヨーは新港にもある、チャリでいけるかも?
(スーパー銭湯の湯快爽快やユニクロやディスカウントのMrMAXなどの複合施設が近くにあります)
http://www.keiyo.co.jp/map/chiba/images/121sinminato08.07.jpg
http://www.yukaisoukai.com/mih/info/accsess/index.html

規模で言うとビバホーム(但し、電車が京葉線の南船橋になるため条件似合わないが、ちなみに南船橋にはIKEAもあるが・・)
http://shop.vivahome.co.jp/user/svh/shinnarashino_svh/access.htm

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ランキング

おすすめ情報