7

C/C++ で与えられた 2 つの制限の間でランダムな素数を生成できる組み込み関数はありますか?

100万から10億の間のランダムな素数を生成できる関数が欲しい

4

3 に答える 3

11

次のように効率的に行うことができます。

  1. その間隔で乱数を生成します。
  2. 最初のいくつかの素数のいずれかで割り切れるかどうかを確認します (たとえば2 .. 17、最良の結果を得るために実験します)。はいの場合は、1 に進みます。
  3. Miller-Rabinを使用して素数性をテストします。

同様の、もう少し複雑なアイデアについては、こちらも参照してください。

于 2012-12-02T01:19:09.583 に答える
3

これを行う必要が生じたとき、isPrime() という関数を作成しました。isPrime() は、数値が素数かどうかをチェックして判断します。

isPrime() には 2 つの異なる関数がありました。1 つは永久に実行され、すべての素数を出力し、もう 1 つは特定の数まで実行されます。

i と j の間のすべての素数を配列に取り込むことができます。次に、配列のサイズ以下の乱数を生成します。この乱数を使用して、配列から要素を選択します。

お役に立てれば！

于 2012-12-02T01:12:59.483 に答える
3

2 つの境界の間で乱数を生成するには、次のようにします。

extern unsigned int urand();
int lower = 1000000;
int upper = 1000000000;
int p = urand() % (upper - lower) + lower;

10 億に近い数が素数であるかどうかをテストするには、sqrt(10 億) = 31622 未満のすべての素数で除算を試行するだけで十分です。このような素数は約 3400 あります。配列を作る

unsigned short primes[3400] = { 2, 3, 5, .. 31657 }

そしてそれらすべてで割ります。すべての試行除算の余りが != 0 の場合、その数は素数です。

このような小さな素数に対して、より洗練された素数性テストが高速になるとは思えません。

于 2012-12-02T04:23:10.030 に答える