2

私は Java の初心者で、クラスの課題の 1 つは、273042282802155991 を含む 100 桁以上の素数を見つけることです。

私はこれまでのところこれを持っていますが、コンパイルして実行すると、連続ループになっているようです。

何か悪いことをしたかどうかはわかりません。

public static void main(String[] args) {
    BigInteger y = BigInteger.valueOf(304877713615599127L);
    System.out.println(RandomPrime(y));
}

public static BigInteger RandomPrime(BigInteger x)
{
    BigInteger i;

    for (i = BigInteger.valueOf(2); i.compareTo(x)<0; i.add(i)) {
        if ((x.remainder(i).equals(BigInteger.ZERO))) {
            x.divide(i).equals(x);
            i.subtract(i);
        }
    }
    return i;
}
4

3 に答える 3

4

ヒントの 1 つは、これらのステートメントは何もしないということです。

x.divide(i).equals(x);
i.subtract(i);

forループの一部と同じ：

i.add(i)

それらはインスタンス自体を変更しませんが、新しい値を返します-チェックして何もしない値です。 BigIntegers「不変」です。変更することはできませんが、操作して新しい値を返すことはできます。

実際にこのようなことをしたい場合は、次のことを行う必要があります。

i = i.add(i);

また、なぜiから引くのでしょうiか? これが常に 0 であることを期待していませんか?

于 2011-12-10T02:26:56.613 に答える
4

これは宿題なので...

  1. 素数性をテストする BigInteger のメソッドがあります。これは、数値を因数分解しようとするよりもはるかに高速です。(100 桁の数を因数分解しようとするアプローチを取ると、失敗します。因数分解はNP 完全問題であると考えられています。確かに、既知の多項式時間解はありません。)

  2. 質問は、一連の 10 進数として表されるときに、特定の一連の数字を含む素数を求めています。

  3. 「ランダムな」素数を生成し、それらの数字が含まれているかどうかをテストするアプローチは実行不可能です。(いくつかの簡単な高校の数学では、ランダムに生成された 100 桁の数に、指定された 18 桁のシーケンスが含まれる確率は ... 82 / 10 18であることがわかります。また、素数性についてはまだテストしていません...

  4. しかし、それを行う別の方法があります...考えてみてください！

アルゴリズムがどのように機能するかを頭の中で理解し、頭の中で見積もりを行って、妥当な時間内に答えが得られることを確認してから、コードを書き始めてください。

私が実行不可能と言うとき、私はあなたにとって実行不可能であることを意味します。十分な数のコンピューター、十分な時間、および強力な数学があれば、これらのことのいくつかを実行できる可能性があります。したがって、技術的には、それらは計算上実行可能である可能性があります。しかし、それらは宿題の練習として実行可能ではありません。この演習のポイントは、これをスマートな方法で行う方法について考えさせることだと確信しています...

于 2011-12-10T02:30:25.940 に答える
0

ミラーラビンアルゴリズムを実装/使用する必要があります

応用暗号ハンドブック

章 4.24 http://www.cacr.math.uwaterloo.ca/hac/about/chap4.pdf

于 2011-12-10T02:50:10.317 に答える