如何判断一个数是否是素数

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的东西，它会说它是一个质数，但它不是。我认为问题是，中断是在一个循环后停止它，所以它不是增加变量p，所以它只是测试除以2(我认为)。但是，如果我删除断点，它将在每次传递时打印出"总和是/不是素数"，直到退出循环。不知道该怎么做。

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
    }

希望这对您有所帮助

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

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

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

为了效率，你不需要检查所有小于sum的数的可整除性，检查所有小于sum的平方根的数就足够了。

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

下面是一个实现这两者的例子。

 // 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

小素数

使用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);

它以这样的方式使用米勒-拉宾概率检验结果是保证的:它使用第一个素数作为连续的(参见Menezes的《应用密码学手册》，表4.1/140页)。

大素数

如果你正在寻找大于Integer.MAX_VALUE的素数:

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

   如果这个BigInteger可能是素数返回true，如果是绝对复合。如果确定性≤0，则返回true。参数:确定性——衡量调用者的不确定性愿意容忍:如果调用返回真的概率是多少这个BigInteger是质数超过(1 - 1/2确定性)。执行此方法的时间与该参数的值成正比。

2. 下次使用"AKS素数性测试";检查候选是否确实是素数。

Answer 5

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

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 &
2. 它将只对奇数运行for循环。
3. 将for循环变量增加2而不是1。
4. 它只迭代for循环到number的平方根，而不是到number。

解释- - - - - -:

我已经提到了以上四点，我将逐一解释。必须为无效输入而不是仅为有效输入编写适当的代码。到目前为止，任何答案都被限制在数字iNum >=2的有效输入范围内。

我们应该知道只有奇数才能是素数， 注意-:2是唯一的偶数素数。所以不能对偶数运行for循环。

我们不能对i变量的偶数值运行for循环，因为我们知道只有偶数才能被偶数整除。我在上面已经提到过，除了2是偶数之外，只有奇数可以是素数。所以不需要在for循环中运行代码，因为for 中变量i的值是偶数。

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

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类的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