如何判断一个数是否为质数

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（我认为）。但是，如果我删除断点，它将在每次通过时打印出 "The sum is/is not a prime number" 直到退出循环。不知道在这里做什么。

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 = 和的平方根。所以使用这种方法你的 for 循环将如下所示：

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

希望对您有所帮助

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."); 
}

Answer 3

你是对的，目前你的代码测试除以二，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.");
 }

Answer 4

到目前为止已经发布了很多正确的答案，但其中 none 已经过优化。这就是为什么我想在这里与您分享优化的代码来确定素数。请查看下面的代码片段...

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;
}

Benefits of above code-:

它也适用于负数以及 0 和 1。
它将运行 for 循环仅用于奇数。
它会将 for 循环变量递增 2 而不是 1。
它将迭代 for 循环直到数字的平方根而不是数字。

Explanation-:

上面提到了四点，我将一一说明。必须为 无效输入适当地编写代码，而不是只为有效输入 编写代码。到目前为止所写的任何答案都限于有效输入范围，其中数字 iNum >=2.

我们应该知道只有奇数可以是质数,注-: 2是唯一的偶数. 所以我们不能运行 for 循环偶数。

我们不能运行 for 循环获取其变量i 的偶数值，因为我们知道只有偶数可以被偶数除。我在上面已经提到只有奇数可以是质数，除了 2 是偶数。 因此无需运行在 for 循环中为 for.

中变量 i 的偶数值编写代码

我们应该迭代 for 只循环到 平方根 的数字而不是 upto 数字。很少有答案实现了这一点，但我还是想在这里提一下。

Answer 5

小质数

使用Apache Commons Math primality test, method is related to prime numbers in the range of int. You can find source code on 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);

It uses the Miller-Rabin probabilistic test in such a way that a result is guaranteed: it uses the firsts prime numbers as successive base (see Handbook of applied cryptography by Menezes, table 4.1 / page 140).

大质数

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

使用BigInteger#isProbablePrime(int certainty)预验证主要候选

Returns true if this BigInteger is probably prime, false if it's definitely composite. If certainty is ≤ 0, true is returned. Parameters: certainty - a measure of the uncertainty that the caller is willing to tolerate: if the call returns true the probability that this BigInteger is prime exceeds (1 - 1/2certainty). The execution time of this method is proportional to the value of this parameter.
接下来使用"AKS Primality Test"检查候选是否确实是素数。

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;
}

Answer 7

您可以使用 Java BigInteger class' 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

如何判断一个数是否为质数

How to determine if a number is prime

java

eclipse

primes

loops

小质数

大质数