素因数の性質。これわどうなっているですか？

600851475143の素因数を探し出す場合です。

・まずxに600851475143を代入しますね
・iに2を代入します

--------------------xが1以上の場合は繰り返し

・x / iで割り切れる場合はxは600851475143の素因数
--xを出力
--x = x/i

・x/iで割り切れない場合は
-- i = i + 1

----------------------繰り返し

xで出力した値　71, 839, 1471, 6857

全然分かりません

600851475143の素因数は
600851475143の約数であり
且つ、その数値が素数であることが条件のはずです。
どうして上のような公式で解けるのでしょうか？


target = 600851475143

x = target
i = 2
prime_factors = []
while x > 1:
if x % i == 0:
prime_factors.append(i)
x = x / i
else:
i += 1

result = max(prime_factors)
print( result )
print (prime_factors)

No.1 ベストアンサー 回答者： ざわざわざわ 回答日時： 2016/08/03 18:51

以下、1は約数といわないということにします。

#1 targetの最小の約数を探す
これを素因数とする。

#2 targetを素因数で割った商X1の
最小の1以外の約数を探す
これを素因数とする。

#3　targetを素因数で割った商X2の
最小の約数を探す
これを素因数とする。

以下同様の作業をXnが1になるまで続ける。


このプログラムの妥当性について

#1　最小の約数=最小の素因数
がなりたつので ok

最小の約数は必ず素数です。
　　最小の約数が6とかいうこと
はありえません。
　　2とか3もでできてしまうからです。

#2　#1で見つけた素数をp1として、
　　target=p1*X1　これの素因数は
　　p1とX1の素因数なので、
X1の素因数を探します。
　　X1の最小の約数を探していくの
　　ですが、これはp1以上のものから
　　探していけばいいでしょう。
　　なぜならば、p1は最小だからです。

#3　は#2と同様ですね。


割った余りが１の所までいけば、
target=p1*p2*p3*…*pn*1と表せる
ことになり、
素因数はp1からpnでつくされることが
わかります。

この回答へのお礼

すっごいですね。

頭悪いので最初は全然分かりませんでしたが
3時間くらい掛けてやっと飲み込めました

一度理解してしまえばかなりわかり易い説明ですね。

ありがとうございました。

お礼日時：2016/08/04 01:13

No.2 回答者： t_fumiaki 回答日時： 2016/08/03 18:51

Xを2,3,4,5,6・・・で次々に割ってみて、割りきれた数(i)が素因数。

こういう論法でしょう？
有ってますよ。
割り切れたからXの約数。

それまでの因数(i)で割り切れなかったのだから素数。
例えば71。
71が素数で無かったら、71は71より小さい整数でm×n・・・×kとかに書ける。
だとしたらiが71に到達する前にm,n,・・・,ｋで割り切れてしまうでしょう？

839だって同じ。
iが839に到達する前に、839の約数で割り切れてしまうでしょう？

２から順にやって割り切れずにiが71まで来てやっと割り切れたんだから、7１は素数なんですよ！！！

この回答へのお礼

ありがとうございます。

お礼日時：2016/08/04 01:09