0

5億未満の数があり、効率的な方法で因数分解したいと思います。どのアルゴリズムを提案しますか？注：制限時間は0.01秒です。

私はこのC++コードを書いたばかりですが、それは絶対にひどいです！

void factorize(int x,vector<doubly> &factors)
{
  for(int i=2;i<=x;i++)
    {
      if(x%i==0)
    {
      doubly a;
      a.number=i;
      a.power=0;
      while(x%i==0)
        {
          a.power++;
          x/=i;
        }
      factors.push_back(a);
    }
    }
}

そして二重にこのようなものです：

struct doubly
{
  int number;
  int power;
//and some functions!!

};

もう1つのポイント：nは素数ではないことを私は知っています

4

5 に答える 5

1

ご存知かもしれませんが、因数分解は難しい問題です。また、素数で割り切れる可能性をテストするだけでよいことも知っているかもしれません。小さいながらもよく知られているヒント: n の平方根までテストするだけで済みます。理屈はあなたに任せます。

エラトステネスのふるいを見てください。そして、これらの質問と回答にヒントが見つかるかも？あれはどうですか？

この回答の空間/時間の完全なトレードなしで、これをより高速にしたい場合は、5億の平方根までのすべての素数を事前に計算し、それらを配列に入れます。明らかに、これは上限が大きくなると壊れます;)

于 2010-08-27T09:47:13.433 に答える
0

アルゴリズムの研究を開始します。
最速の因数分解アルゴリズムは何ですか?

于 2010-08-27T09:49:34.503 に答える
0

500,000,000 までのすべての整数を事前に因数分解し (方法は関係ありません)、因数をデータベースまたは固定長レコード形式に格納します。ルックアップは高速で、データベースは最新の PC に適合する必要があります。

これは時間と空間のトレードオフの 1 つの目的ですが、何を最適化しようとしているのかについては言及していません。

あるいは、GNU coreutils の「factor」のアルゴリズムを見てください。

于 2010-08-27T09:52:07.213 に答える
0

Pollard の rho ヒューリスティックを試すことができます。これは、除数が比較的小さい複素数に適しています。

ポラードのロー

于 2010-08-27T09:52:11.190 に答える
0

これが宿題である場合は、講義資料を読み直した方がよいと思います。

とにかく、あなたの数は複合的で非常に小さいことを知っています。それで問題ありません。

すべての数値を使用した単純な試行分割の場合、最大で sqrt(500000000) テストが必要です。最悪の場合は約 22360 回です。偶数は 2 で割り切れるので、明らかにスキップできます (最初に確認してください)。したがって、これは 0.01 秒で 11180 分割になります。お使いのコンピューターが 1 秒あたり 110 万分割を実行できる場合は、単純なアプローチを使用できます。

または、sqrt(500M) までの素数のリストをオフラインで作成し、それらのそれぞれを試してみることもできます。これにより、分割がさらに削減されます。

または、因子が互いに離れすぎていない場合は、フェルマーの方法を試すことができます。

これらが機能しない場合は、Pollard の rho などを使用してみてください。

または、これが宿題でない場合は、制限を回避するために問題をもう一度説明してください（一部の人が示唆しているように、因数分解された数値を事前に計算できますかなど）。

于 2010-08-27T12:58:35.960 に答える