プログラム的に大きな数値を因数分解する

いいえ、私は巨大な数字fを持っています。この数字は100桁を少し上回っています。私は要因がほぼ同じサイズであることを知っています。プログラム的に大きな数値を因数分解する

リソースと時間が限られている場合、どの言語とアルゴリズムを使用する必要がありますか？制限時間内にアルゴリズムをコーディングする時間を含めています。

思考？

編集：限られた意味で、私は可能な限りの時間を意味します。

出典

2012-01-15 tekknolagi

@Mysticial面白いですが、役に立たないです。 – tekknolagi

クラウドコンピューティングのための良い練習のように聞こえる。これは、並列処理を容易に実行できるはずです。（限られた時間に会いますが、限定されたリソースではないかもしれません...） – ziesemer

@ziesemer興味深い考え方 - これはクラウドコンピューティングについてどう思いますか？私はいくつかのサーバーを持っています。 – tekknolagi

最先端のプライムの因数分解アルゴリズムはquadratic sieveとそのですバリアント。 100桁を超える数値の場合、number sieveがより効率的になります。

オープンソースの実装はhereです。それは4 hours on a 2.2 GHz AMD Althonの2つのおおよそ等しい素数に100桁の数を因数分解することができます。

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

出典

2012-01-15 06:50:18 Mysticial

数字フィールドのふるいを二次ふるいの変形と見なしますか？ –

しかし、2つの間のカットオフしきい値は、とにかく約100桁です。私はそれを私の答えに加えます。ありがとう。 – Mysticial

これは、クラウドコンピューティングのための良い練習（おそらくまれな良い例）のように聞こえます。これは、並列処理を容易に実行できるはずです。それぞれのプロセスに要因のプールを分けます。

次のようなものが役立つ場合があります。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-15 06:40:06 ziesemer

「要因のプール」とはどういう意味ですか？私は1つの番号しか持っていません。 – tekknolagi

@tekknolagi - 数字は1つありますが、多くの可能な要素（探しているもの）があります。 – ziesemer

真、真。因数分解の実際の分割に関する詳細はありますか？ – tekknolagi

-2

while (x < Number) { 
    if ((Number % x) == 0) { 
     cout << x << "*" << Number/x << endl; 
     ++x; 
    } 
    else ++x; 
}

出典

2012-01-15 06:43:34 MVTC

OPの＃がintの内部に収まりません。 – ziesemer

あなたが冗談か真剣なのか分かりません。 – st0le

彼は冗談を言っていません。彼はbigint型のネイティブサポートを持つコンパイラを使用しており、さまざまな最適化を使ってコードをコンパイルしています。 :) –

プログラム的に大きな数値を因数分解する

答えて

関連する問題