アカウント名:
パスワード:
この質問 [yahoo.co.jp]ですかね?誤った回答に対してベストアンサーが付くのは、実にYahoo知恵袋。
それはさておき、フェルマー法はN = a2 - b2 = (a+b)(a-b)という形で素因数を探す、という点ではaとbとのどちらをループ回しても同じですが、アルゴリズム的には上からやるものだと思います。302 - 893 = 7 : 平方数でない312 - 893 = 68 : 平方数でない322 - 893 = 131 : 平方数でない332 - 893 = 196 : 平方数 142 → 893 = 332 - 142 = (33+14)(33-14) = 47 × 19って感じ。
その試行回数は、Nから偶数は除外しておくと、3の倍数つまり a+b=N/3、a-b=3 になるのが最悪ケースで、a=N/6+3/2、b=N/6-3/2です
>aを√Nから増やす方法フェルマー法初めて知って1²から試していたが減らしていくなら√NからではなくN/2以上の最小の整数じゃないか。N=892の時、√892=29.86...、892/2=246892=(224+222)(224-222)=2×446
1²から試していくと大きさの近い約数が2つが取れる利点がありそう。あと4で割り切れない偶数はフェルマー法で因数分解できないのかな?
4で割り切れない偶数は、因数分解できない。なぜならa+bとa-bは、その両方が偶数か、両方が奇数であって、整数の範囲では片方偶数片方奇数になることはないから。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
身近な人の偉大さは半減する -- あるアレゲ人
フェルマー法って効率悪いっすよね (スコア:1)
この質問 [yahoo.co.jp]ですかね?
誤った回答に対してベストアンサーが付くのは、実にYahoo知恵袋。
それはさておき、フェルマー法は
N = a2 - b2 = (a+b)(a-b)
という形で素因数を探す、という点ではaとbとのどちらをループ回しても同じですが、
アルゴリズム的には上からやるものだと思います。
302 - 893 = 7 : 平方数でない
312 - 893 = 68 : 平方数でない
322 - 893 = 131 : 平方数でない
332 - 893 = 196 : 平方数 142
→ 893 = 332 - 142 = (33+14)(33-14) = 47 × 19
って感じ。
その試行回数は、Nから偶数は除外しておくと、
3の倍数つまり a+b=N/3、a-b=3 になるのが最悪ケースで、a=N/6+3/2、b=N/6-3/2
です
Re:フェルマー法って効率悪いっすよね (スコア:1)
>aを√Nから増やす方法
フェルマー法初めて知って1²から試していたが減らしていくなら√NからではなくN/2以上の最小の整数じゃないか。
N=892の時、√892=29.86...、892/2=246
892=(224+222)(224-222)=2×446
1²から試していくと大きさの近い約数が2つが取れる利点がありそう。
あと4で割り切れない偶数はフェルマー法で因数分解できないのかな?
Re: (スコア:0)
4で割り切れない偶数は、因数分解できない。
なぜならa+bとa-bは、その両方が偶数か、両方が奇数であって、整数の範囲では片方偶数片方奇数になることはないから。