6

よし、それで私は膨大な数を持っているf。この数字は、実際には 100 桁を少し超えています。因子はほぼ同じサイズであることがわかっています。

リソースと時間が限られている場合、どの言語とアルゴリズムを使用すればよいですか? 限られた時間にアルゴリズムをコーディングする時間の長さを含めています。

考え？

編集: 制限付きとは、可能な限り短い時間を意味します。

4

3 に答える 3

8

最先端の素因数分解アルゴリズムは、二次ふるいとその変形です。100 桁を超える数値の場合、数値ふるいがより効率的になります。

ここにオープンソースの実装があります。2.2 GHz AMD Althonでわずか 4 時間で、100 桁の数を 2 つのほぼ等しい素数に因数分解できます。

アルゴリズムとサンプル実装があります。それはあなたにアイデアを与えたり、始めたりするのに十分かもしれません.

于 2012-01-15T06:50:18.457 に答える
1

これは、クラウド コンピューティングの良い例のように思えます (そして、おそらく稀な良い例です)。これは、並列処理を実行しやすいはずです。因子のプールを各プロセスに分割します。

http://blog.controlgroup.com/2010/10/13/hadoop-and-amazon-elastic-mapreduce-analyzing-log-files/ 詳細については、http://en.wikipediaを 参照してください。 org/wiki/Apache_Hadoop#Hadoop_on_Amazon_EC2.2FS3_services .

(先月、私がここで提案しているものと同様のドーミングの素晴らしいビデオ デモンストレーションを見ましたが、もちろん、今はリンクが見つかりません。)

特に、これをプログラムで行う必要がない場合は、http://www.alpertron.com.ar/ECM.HTMをご覧ください。( http://en.wikipedia.org/wiki/Quadratic_sieveからリンクされています。) 最初のリンクの「複数のマシンで数を因数分解する」の下にある注意事項に特に注意してください。(ソースコードが利用可能であるため、Hadoop などを使用して、これをプログラム的に分散した方法で実行することもできます。)

于 2012-01-15T06:40:06.763 に答える
-2 
while (x < Number) {
    if ((Number % x) == 0 ) { 
        cout << x << "*" << Number/x << endl;
        ++x;
    }  
    else ++x;
}
于 2012-01-15T06:43:34.190 に答える