6

因数分解を実装する方法については多くの質問がありますが、本番環境で使用する場合は、オープン ソース ライブラリを使用して、効率的で十分にテストされたものをすぐに取得したいと考えています。私が探している方法は次のようになります。

static int[] getPrimeFactors(int n)

n=12 の場合、{2,2,3} を返します。

ライブラリには、long 型または BigInteger 型を処理するためのオーバーロードもある場合があります。

問題は特定のアプリケーションに関するものではなく、この問題を適切に処理するライブラリを持つことです。多くの人は、数値の範囲に応じて異なる実装が必要であると主張していますが、この点に関しては、ライブラリが実行時に最も合理的な方法を選択することを期待しています。

効率的とは、「世界最速」という意味ではありません (そのための JVM では作業しません...)。int と long range を 1 時間ではなく 1 秒以内に処理することを意味します。

4

4 に答える 4

4

それはあなたが何をしたいかによります。必要性がさほど高くない場合 (たとえば、 Project Eulerの問題を解決したい場合)、Pollard の rho アルゴリズムを簡単に実装すると、最大 10 桁または 12 桁の因数を即座に見つけることができます。それが必要な場合はお知らせください。コードを投稿できます。Java で書かれたより強力なファクタリング プログラムが必要な場合は、Dario Alpern のアプレットの背後にあるソース コードを見ることができます。テスト スイートについては知りませんが、実際にはオープン API を使用して設計されていませんが、多くのユーザーがいて、十分にテストされています。負荷の高いオープンソースのファクタリング プログラムのほとんどは C または C++ で書かれており、GMP の big-integer ライブラリを使用していますが、言語の外部関数インターフェイスを介してそれらにアクセスできる場合があります。msieve、pariまたはyafu。これらに満足できない場合は、Mersenne Forumでさらに支援を求めることができます。

于 2012-07-23T14:23:57.560 に答える
1

問題を解決したい場合は、求めているものを取得するのではなく、テーブルが必要です。ばかげた遅い方法を使用して事前計算し、保存してから、マイクロ秒単位で任意の数の係数を調べることができます。特に、数値に対応するインデックスに最小の因数がリストされているテーブルが必要です。試行除算を使用して最小の素数をいくつか削除すると、メモリ効率が大幅に向上します。次に、テーブルを下に移動して、あなたは1を打ちます（これ以上除数がないことを意味します;あなたが残したものは素数です）。これは、テーブルエントリごとに2バイトしかかかりません。つまり、スマートフォンよりも重い最新のマシンにすべてを保存できます。

興味がある場合は、これを作成する方法を示し、アクティブなコミュニティと複雑なアルゴリズムの単体テストで達成できるよりも高い信頼性で正しいことを確認する方法を示します（生成するアルゴリズムを実行した場合を除く）このテーブルとそれがすべて大丈夫であることを確認しました）。

于 2012-07-23T17:25:40.687 に答える
0

多項式がプリミティブかどうかをテストするために必要です。

これは、すべての数の因数を見つけようとするよりも高速です。

public static boolean gcdIsOne(int[] nums) {
    int smallest = Integer.MAX_VALUE;
    for (int num : nums) {
        if (num > 0 && smallest < num)
            smallest = num;
    }
    OUTER:
    for (int i = 2; i * i <= smallest; i = (i == 2 ? 3 : i + 2)) {
        for (int num : nums) {
            if (num % i != 0)
                continue OUTER;
        }
        return false;
    }
    return true;
}
于 2012-07-23T14:06:15.977 に答える
-2

この関数をscalaで試しました。ここに私の結果があります：

def getPrimeFactores(i: Int) = {
  def loop(i: Int, mod: Int, primes: List[Int]): List[Int] = {
    if (i < 2) primes      // might be i == 1 as well and means we are done
    else {
      if (i % mod == 0) loop(i / mod, mod, mod :: primes)
      else loop(i, mod + 1, primes)
    }
  }
  loop(i, 2, Nil).reverse
}

できるだけ機能的になるようにしました。
if (i % mod == 0) loop(i / mod, mod, mod :: primes)除数が見つかったかどうかを確認します。もしそうなら、それを素数に加えて、i を mod で割ります。
新しい除数が見つからない場合は、除数を増やします。
loop(i, 2, Nil).reverse関数を初期化し、結果を徐々に順序付けます。

于 2012-07-23T12:14:22.970 に答える