7

私は非常に大きな数の最大の素因数を見つけるプログラムを書こうとしていますが、さまざまな成功を収めたいくつかの方法を試しました。私がこれまでに見つけたものはすべて、信じられないほど遅いものでした。私は考えましたが、これが有効なアプローチであるかどうか疑問に思っています。

long number = input;

while(notPrime(number))
{
    number = number / getLowestDivisiblePrimeNumber();
}

return number;

このアプローチは入力を受け取り、次のことを行います。

200-> 100-> 50-> 25-> 5（リターン）

90-> 45-> 15-> 5（リターン）

currentNum自体が素数になるまで（ほとんどの場合2、または3）、currentNumを最小の除算数（ほとんどの場合2、または3）で繰り返し除算し、これが元の入力の最大の素因数であると想定します。

これは常に機能しますか？そうでない場合、誰かが私に反例を与えることができますか？

-

編集：非常に大きいとは、約2 ^ 40、つまり10^11を意味します。

4

6 に答える 6

25

この方法は機能しますが、時間がかかります。「あなたの数はどれくらいですか？」使用する方法を決定します。

于 2009-12-09T22:19:38.977 に答える
17

これは、一意のプライムファクタリング定理のために常に機能します。

于 2009-12-09T22:10:25.033 に答える
3

確かに機能しますが（Mark Byersの回答を参照）、「非常に大きな」入力の場合は、時間がかかりすぎる可能性があります。別のループを隠すための呼び出しgetLowestDivisiblePrimeNumber()はO（N ^ 2）で実行されるため、「非常に大きい」という意味によっては、遅いBigNumで動作する必要がある場合があることに注意してください。

アルゴリズムが最後に見つかったものよりも小さい係数をチェックする必要がないことに注意することで、少しスピードアップできます。

于 2009-12-09T22:17:26.383 に答える
2

あなたは数の素因数を見つけようとしています。あなたが提案していることはうまくいくでしょうが、それでも多数の人にとっては遅いでしょう....ほとんどの現代のセキュリティはこれが難しい問題であることを前提としているので、これに感謝する必要があります。

于 2009-12-09T22:17:25.357 に答える
1

私が行ったクイック検索から、数値を因数分解する最も速い既知の方法は、楕円曲線法を使用することです。

あなたはこのデモであなたの番号を投げることを試みることができます：http：//www.alpertron.com.ar/ECM.HTM。

それがあなたを納得させるなら、あなたはコードを盗むか（それは面白くない、彼らはそれへのリンクを提供する！）、あるいは他の場所でそれの理論を読むことを試みることができる。ここにそれについてのウィキペディアの記事があります：http：//en.wikipedia.org/wiki/Lenstra_elliptic_curve_factorizationしかし、私はそれを理解するにはあまりにも愚かです。ありがたいことに、それはあなたの問題であり、私の問題ではありません！:)

于 2009-12-09T22:40:55.410 に答える
0

Project Eulerの特徴は、通常、問題を実行するための明白なブルートフォース方式が存在することです。これには、ほぼ永久に時間がかかります。質問が難しくなるにつれて、賢い解決策を実装する必要があります。

この問題を解決する1つの方法は、数値の最小（正の整数）の因数を常に見つけるループを使用することです。数の最小の因数がその数であるとき、あなたは最大の素因数を見つけました！

詳細なアルゴリズムの説明：

これを行うには、次の3つの変数を保持します。

因数分解しようとしている数（A）現在の除数ストア（B）最大の除数ストア（C）

最初に、（A）を関心のある数値とします。この場合は600851475143です。次に（B）を2とします。（A）が（B）で割り切れるかどうかをチェックする条件を設定します。除算可能な場合は、（A）を（B）で除算し、（B）を2にリセットして、（A）が（B）で除算できるかどうかの確認に戻ります。それ以外の場合、（A）が（B）で割り切れない場合は、（B）を+1でインクリメントしてから、（A）が（B）で割り切れるかどうかを確認します。（A）が1になるまでループを実行します。返される（3）は、600851475143の最大の素数除数になります。

これをより効果的にする方法はたくさんあります。次の整数にインクリメントする代わりに、次の必然的に素数の整数にインクリメントできます。最大の除数ストアを保持する代わりに、除数が唯一の場合に現在の数値を返すことができます。自体。ただし、上記のアルゴリズムは、関係なく数秒で実行されます。

Pythonでの実装は次のとおりです。-

def lpf(x):
        lpf = 2;
        while (x > lpf):
                if (x%lpf==0):
                        x = x/lpf
                        lpf = 2
                else:
                        lpf+=1;
        print("Largest Prime Factor: %d" % (lpf));

def main():
        x = long(raw_input("Input long int:"))
        lpf(x);
        return 0;

if __name__ == '__main__':
    main()

例：上記の方法を使用して、105の最大の素因数を見つけましょう。

（A）= 105とします。（B）= 2（常に2から開始します）、（C）の値はまだありません。

（A）は（B）で割り切れますか？いいえ。（B）を+1でインクリメントします：（B）=3。（A）は（B）で割り切れますか？はい。（105/3 = 35）。これまでに見つかった最大の除数は3です。（C）= 3とします。更新（A）= 35。リセット（B）=2。

さて、（A）は（B）で割り切れますか？いいえ。（B）を+1でインクリメントします：（B）=3。（A）は（B）で割り切れますか？いいえ。（B）を+1でインクリメントします：（B）=4。（A）は（B）で割り切れますか？いいえ。（B）を+1でインクリメントします：（B）=5。（A）は（B）で割り切れますか？はい。（35/5 = 7）。以前に見つけた最大の除数は（C）に格納されています。（C）は現在3です。5は3より大きいため、（C）= 5を更新します。（A）=7を更新します。（B）=2をリセットします。

次に、（A）のプロセスを繰り返しますが、7は素数であり、それ自体と1以外の除数がないため、（B）=（A）まで（B）をインクリメントし続けます。 ）>（（A）/ 2）、数値の半分を超える整数の約数を持つことはできないため、任意の数の可能な最小の約数（1以外）は2です！）

したがって、その時点で（A）=7を返します。

これらのいくつかを手作業で試してみてください。そうすれば、アイデアのコツをつかむことができます。

于 2015-07-27T13:03:36.097 に答える