如何确定一个数是质数

Question

好的，我的问题不是如何确定一个数字是否为质数，因为我认为我已经解决了这个问题，而是如何使其正确显示。

这是我的代码：

public static void main(String[] args) {
    // Declare Variables
    int randomNumbers = 0;
    int sum = 0;
    //Loop for number generation and print out numbers
    System.out.print("The five random numbers are: ");
    for (int i = 0; i <= 4; i++)
    {
        randomNumbers = (int)(Math.random()*20);
        sum += randomNumbers;

        if (i == 4) {
            System.out.println("and " + randomNumbers + ".");
        }
        else {
            System.out.print(randomNumbers + ", ");
        }
    }
    //Display Sum
    System.out.println("\nThe sum of these five numbers is " + sum + ".\n");

    //Determine if the sum is prime and display results
    for(int p = 2; p < sum; p++) {
        if(sum % p == 0)
            System.out.println("The sum is not a prime number.");
        else 
            System.out.println("The sum is a prime number.");
        break;
        }
    }


}

现在我的问题是，如果数字结尾是9之类的数字，它会说它是一个质数，但实际上它不是。我认为问题是 break 语句只停止了一次循环，所以它没有增加变量p，所以它只测试被2整除（我想）。但是，如果我移除 break 语句，它会在每个通过的时候打印出“总和是/不是质数”，直到退出循环。不确定该怎么做。

- senpaimaster

Answer 1

您的判断数字是否为质数的方法是正确的。

为了使其不会一直输出数字是不是质数，您可以使用一个外部变量来表示数字是否为质数。

例如：

    boolean prime = true;
    for (int p = 2; p < sum; p++) {
        if (sum % p == 0) {
            prime = false;
            break;
        }
    }
    if (prime)
        System.out.println("The sum is a prime number.");
    else
        System.out.println("The sum is not a prime number.");

通过这种方法，程序会假定该数字是素数，直到证明错误为止。因此，当它发现它不是素数时，它会将变量设置为false并跳出循环。

然后，在循环结束后，您只需打印该数字是否为素数即可。

让循环更快的一种方法是从 p = 2 开始，直到 p = sum 的平方根为止。因此，使用这种方法，for 循环将如下所示：

    double sq = Math.sqrt((double)sum);
    for (int p = 2; p < sq; p++) {
        //Rest of code goes here
    }

希望这可以帮到你。

- creeperdomain

---

非常有帮助，虽然你在那里留下了“break;”，这让我很困惑，直到我意识到我需要把它去掉。非常感谢你的帮助！ - senpaimaster

“break” 的作用是在第一次找到因子时退出循环，因为不需要再继续查找。 - Unamanic

你的逻辑是正确的，但它并不是最优化的。因此，只需迭代到数字的平方根而不是数字本身的大小。并且将 for 循环变量（从3开始）的增量改为2而不是1。我已经发布了一个答案，请参考其中的更多细节。 - Ashish Kumar

最后一个for循环应该包括上限范围，像这样 for (int p = 2; p < sq; p++)否则它将返回不正确的结果，指出4和9是质数。 - Anatolii Stepaniuk

1 不是质数。 如果一个大于1的整数只有1和它本身两个正因子（因数），那么它被称为质数。 - Shawn Tsai

for循环不应该包括平方根：p <= sq吗？如果我们测试例如数字9，上述代码将不会测试9％3，因为循环将在循环体的第一次执行后退出。或者我错过了什么？ - Tuure

Answer 2

你需要在循环外部使用一个布尔值来存储该数字是否为质数：

//Determine if the sum is prime and display results
boolean isPrime = true;
for(int p = 2; p < sum; p++) {
    if(sum % p == 0){
        isPrime = false;
        break;
    }
}
if(isPrime){
   System.out.println("The sum is a prime number.");
} else {
   System.out.println("The sum is not a prime number."); 
}

- Unamanic

---

你的逻辑是正确的，但它不够优化。所以只需迭代到数字的平方根而不是数字本身。并且将 for 循环变量（从 3 开始）的增量改为 2 而不是 1。我已经发布了一个答案，请参考那个以获取更多细节。 - Ashish Kumar

Answer 3

你说得对，目前你的代码测试除以2，而且break命令在一次循环后就停止了。

在循环第一次执行（p==2）之后，break将总是停止循环。

修复代码最快的方法是改变循环部分，像这样：

boolean isPrime=true;
for(int p = 2; p < sum; p++) {
    if(sum % p == 0) {
        isPrime=false;
        System.out.println("The sum is not a prime number.");
        break;
    }
}
if (isPrime)
    System.out.println("The sum is a prime number."); 

这段代码可以提高效率和代码优雅度。

为了提高效率，你不需要检查所有小于和的数字是否可被整除，只需检查所有小于平方根的数字即可。

为了更好的代码，创建一个单独的函数来测试一个数字是否为质数。

这里是一个同时实现两者的例子。

 // tests if n is prime
 public static boolean isPrime(int n) {
     if (n<2) return false;
     for(int p = 2; p < Math.sqrt(n); p++) {
        if(n % p == 0) return false;  // enough to find one devisor to show n is not a prime
     }
     return true; // no factors smaller than sqrt(n) were found
 }

 public static void main(String []args){
    ...
    System.out.println("sum is "+ sum);
    if (isPrime(sum)) 
        System.out.println("The sum is a prime number.");
    else 
        System.out.println("The sum is not a prime number.");
 }

- Yuvalal Liron

---

你在for循环的括号中使用了Math.sqrt(n)，这是不好的做法。它通过一遍又一遍地计算平方根降低了性能。更好的方法是将数字的平方根存储在临时变量中，并在for循环中使用。 - Ashish Kumar

将for循环变量（从3开始）的增量从1改为2。我已经发布了一个答案，请参考那个答案以获取更多细节。 - Ashish Kumar

Answer 4

小质数

使用Apache Commons Math的素数测试，该方法与int范围内的质数有关。您可以在GitHub上找到源代码。

<dependency>
    <groupId>org.apache.commons</groupId>
    <artifactId>commons-math3</artifactId>
    <version>3.6.1</version>
</dependency>

// org.apache.commons.math3.primes.Primes
Primes.isPrime(2147483629);

它使用Miller-Rabin概率测试的方式，以确保结果：它使用最初的质数作为连续的基数（请参见应用密码学手册Menezes, table 4.1 / 第140页）。

大质数

如果您正在寻找大于Integer.MAX_VALUE的质数：

1. 使用 BigInteger#isProbablePrime(int certainty) 预先验证素数候选者

   如果此 BigInteger 可能是质数，则返回 true，如果它绝对是合成的，则返回 false。 如果确定性 ≤ 0，则返回 true。 参数：确定性 - 调用方愿意容忍的不确定性度量：如果调用返回 true，则此 BigInteger 是质数的概率超过 (1-1/2certainty)。 此方法的执行时间与此参数的值成比例。

2. 接下来使用 "AKS 素性测试" 检查候选者是否确实为素数。

- kinjelom

Answer 5

您可以使用Java BigInteger类的isProbablePrime方法来轻松确定并打印这个和是质数还是合数。

 BigInteger number = new BigInteger(sum);
        if(number.isProbablePrime(1)){
            System.out.println("prime");
        }
        else{
            System.out.println("not prime");
        }

您可以在这里阅读更多关于该方法的信息https://docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html#isProbablePrime%28int%29

- Ali Zedan

Answer 6

使用最高效的时间复杂度，即O(sqrt(n))：

public static boolean isPrime(int num) {

    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0) {
            return false;
        }
    }

    return true;
}

- Sameer Shrestha

Answer 7

到目前为止，已经发布了很多正确的答案，但没有一个是优化的。这就是为什么我想在这里与您分享确定质数的优化代码。请看下面的代码片段...

private static boolean isPrime(int iNum) {
boolean bResult = true;
if (iNum <= 1 || iNum != 2 && iNum % 2 == 0) {
    bResult = false;
} else {
    int iSqrt = (int) Math.sqrt(iNum);
    for (int i = 3; i < iSqrt; i += 2) {
    if (iNum % i == 0) {
        bResult = false;
        break;
    }
    }
}
return bResult;
}

以上代码的优点：

1. 它适用于负数、0和1。
2. 它仅对奇数运行for循环。
3. 它将for循环变量增加2而不是1。
4. 它仅在平方根范围内迭代for循环，而不是在整个数字范围内。

解释：

我已经提到了上面的四点，现在逐一解释。代码必须适当地编写以处理无效输入而不仅仅是有效输入。目前为止写出的所有答案都限制在输入范围有效的情况下，其中数字iNum >= 2。

我们应该知道只有奇数才能是质数，注意：2是唯一的偶数质数。因此，我们不应该对偶数运行for循环。

我们不能对变量i的偶数值运行for循环，因为我们知道只有偶数可以被偶数整除。我已经在上面提到，除2以外，只有奇数才可能是质数。因此，在for中不需要对变量i的偶数值运行代码。 我们应该迭代for循环仅到数字的平方根而不是数字本身。一些答案已经实现了这个点，但我还是想在这里提一下。

- Ashish Kumar