正整数Nの最大の素因数を求めるアルゴリズム

質問

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

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

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

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

回答No.5

tar0_puzzle · ベストアンサー

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を比較して大きい方を選べば
最大の素因数が得られることになります
----

回答No.4

tar0_puzzle

リンク先の質問でも答えたのですが
このアルゴリズムは, 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_detail.php?qid=1360012823

回答No.3

nattocurry

a<b<cで、c=a*bだとして、i=cになった時点で、noは素因数にaもbも含まない状態になっているので、aとbの積であるcも当然noの素因数には含まれません。
なので、no%i==0の条件を満たすことはなく、no/=iの処理も行われません。

回答No.2

nattocurry

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には当てはまらないようになっています。

回答No.1

Tacosan

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

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