如何获得 N 位随机 "industrial grade" 素数，其中 5 < N < 20？

Question

这段代码哪里做错了？生成 N 位随机数的更好方法是什么？

public static boolean isPrime(long n) {
if (n <= 3) {
    return n > 1;
} else if (n % 2 == 0 || n % 3 == 0) {
    return false;
} else {
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) {
            return false;
        }
    }
    return true;
}

}

public static long getPrime(int digit){
    long sample;
    long multiple = Math.round(Math.pow(10, digit));
    do{         
        sample = Math.round(Math.random()* multiple);
        //System.out.println(sample);
    }while(!isPrime(sample));
    return sample;
}

Answer 1

What am doing wrong here in this piece of code:

很多东西。

正如评论者指出的那样，您的素数测试在数学上是伪造的。
您实施的测试不正确。 Math.pow(...) 函数 returns 和 double，因此您可能会遭受精度损失。但是你需要完全精确的余数运算（%）才能给你正确的答案。
您忽略了标准 BigInteger class 提供的完美可用的素数生成和素数测试方法；有关详细信息，请参阅 javadoc。

我的猜测是第 2 点是你所缺少的。

Answer 2

您的 getPrime() 方法几乎适用于 5 < N < 19。它不适用于 N = 19，因为最大可能的 long 值是 9223372036854775807，长度为 19 位。它对小于 19 的值不太有效的原因是它可以生成少于所需位数的数字。你需要 while(sample < (long) Math.pow(10, digit - 1) || !isPrime(sample))

现在您已经更新了您的 isPrime() 方法，它几乎可以工作，但您需要更换

for (int i = 5; i * i <= n; i += 6)

来自

for (long i = 5; i * i <= n; i += 6)

否则 i * i 的值可能会溢出。

Answer 3

Math.random() 只有 15-16 位精度，因此不会生成所有 16、17、18、19 或 20 位数字。问题是第 16、17、18、19、20 位数字更有可能分别是 2、4、8、16 和 32 的倍数，因此不是质数。

我建议你使用SecureRandom.nextLong()取低N位。

如何获得 N 位随机 "industrial grade" 素数，其中 5 < N < 20？

How do I get a N digit random "industrial grade" prime number where 5 < N < 20?

java

random

primes