Java 用示例检验素数的程序

什么是质数？

质数是大于 1 的自然数，它只能被 1 或它本身整除。例如，11 只能被 1 或它本身整除。其他质数有 2、3、5、7、11、13、17，这个数列无限不完。

大于 1 的非质数称为合数，因为它可以由更小的因数组成。例如，9 是合数，因为它能被 3 整除；15 是合数，因为它能被 3 和 5 整除。

注意： 0 和 1 都不是质数。2 是唯一的偶质数，负数永远不被认为是质数。

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

验证策略是一个简单的整除性测试。取候选值，依次用每个较小的整数除以它，并检查取模运算符返回的余数。余数为零表明存在除数，这立即排除该数。

程序逻辑：

• 我们需要将一个输入的数字（例如 17）分别除以 2 到 17 之间的任意值，并检查余数。如果余数为 0，则该数字不是质数。
• 没有一个数能被它自身的一半以上整除。所以我们需要 循环 通过只是 numberToCheck/2如果输入为 17，则一半为 8.5，循环将遍历值 2 到 8。
• 如果 numberToCheck 能被另一个数整除，则标志 isPrime 被设置为 false 并退出循环。

二 Java 特征承载着整个算法。取模运算符 % 返回整数除法的余数，以及 break 该语句会在答案确定后立即停止循环，因此不会执行不必​​要的迭代。

Java 检查一个数是否为质数的程序

以下程序将值 17 赋给变量 numberToCheck，并打印出每一步除法运算的结果，以便您可以逐行理解其推理过程。代码是可编辑的，您可以更改值并使用合数（例如 21）再次运行程序，以查看相反的结果。

public class PrimenumberToCheckCheck {

 public static void main(String[] args) {
  int remainder;
  boolean isPrime=true;
  int numberToCheck=17; // Enter the number you want to check for prime

  //Loop to check whether the number is divisible by any number other than 1 and itself
  for(int i=2;i<=numberToCheck/2;i++)
  {
   //number is divided by i
            remainder=numberToCheck%i;
            System.out.println(numberToCheck+" Divided by "+ i + " gives a remainder "+remainder);

       //if remainder is 0 then the number is not prime and we break the loop. Else continue the loop
     if(remainder==0)
     {
        isPrime=false;
        break;
     }
  }
  // Check value true or false, if isPrime is true then the number is prime otherwise not prime
  if(isPrime)
     System.out.println(numberToCheck + " is a Prime number");
  else
     System.out.println(numberToCheck + " is not a Prime number");
    }
  }

预期产量：

17 Divided by 2 gives a remainder 1
17 Divided by 3 gives a remainder 2
17 Divided by 4 gives a remainder 1
17 Divided by 5 gives a remainder 2
17 Divided by 6 gives a remainder 5
17 Divided by 7 gives a remainder 3
17 Divided by 8 gives a remainder 1
17 is a Prime number

循环在第 8 步停止，因为 17 除以 2 等于 8（整数运算）。由于余数始终不为零，标志 isPrime 保持其初始值 true，最终条件输出肯定结果。

使用平方根法的优化素数检验

将数字除以一半是正确的，但很浪费。如果一个数 n 有一个大于其平方根的除数，那么对应的余除数必定小于其平方根，因此早就被找到了。所以，检查到 √n 就能用更少的迭代次数得到相同的结果。

public class PrimeCheckOptimized {

    public static boolean isPrime(int n) {
        // 0, 1 and negative values are never prime
        if (n <= 1) {
            return false;
        }
        // 2 is the only even prime number
        if (n == 2) {
            return true;
        }
        if (n % 2 == 0) {
            return false;
        }
        // test only odd divisors up to the square root
        for (int i = 3; i * i <= n; i += 2) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int[] samples = {1, 2, 9, 17, 97};
        for (int value : samples) {
            System.out.println(value + " is prime: " + isPrime(value));
        }
    }
}

输出：

1 is prime: false
2 is prime: true
9 is prime: false
17 is prime: true
97 is prime: true

条件 i * i <= n 避免了对 Math.sqrt 进行浮点运算，步长为 2 则跳过了所有偶数除数。对于像 1,000,003 这样的值，基本循环大约需要执行 500,000 次迭代，而此版本只需不到 500 次。

检查用户输入的质数

硬编码输入对于演示来说很方便，但实际练习通常需要键盘输入。Scanner 类从控制台读取一个整数，并将其传递给同一个 isPrime 方法。

import java.util.Scanner;

public class PrimeCheckUserInput {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter a number: ");
        int number = sc.nextInt();

        boolean isPrime = number > 1;
        for (int i = 2; i * i <= number; i++) {
            if (number % i == 0) {
                isPrime = false;
                break;
            }
        }

        System.out.println(number + (isPrime ? " is a Prime number" : " is not a Prime number"));
        sc.close();
    }
}

示例运行：

Enter a number: 29
29 is a Prime number

编写素数程序时常见的错误

大多数错误提交都发生在边界值上，而不是主循环上。以下列表涵盖了初学者代码中最常见的错误。

1. 循环从 1 开始： 每个整数都能被 1 整除，因此该标志立即被设置为 false，程序报告说没有质数。
2. 将 1 视为质数： 值 1 只有一个除数，因此它不符合两个除数的定义，必须返回 false。
3. 省略 break 语句： 程序仍然会返回正确答案，但在结果出来后仍然会继续迭代，这在处理大型输入时会浪费时间。
4. 运用 i <= n 作为边界： 这个数总是能整除自身，所以循环必须在到达 n 之前停止。
5. 比较 = 而不是 ==: 单个等号会赋值而不是测试值，这会在 if 条件中产生编译时错误。

素数检验方法的比较

选择与输入大小相匹配的方法，并确定是要测试一个值还是一个范围。

当需要对整个范围而非单个值进行分类时，筛法效率更高。我们的配套程序用于查找 总理 Numbers 从1到100 这证明了这种模式。有关相关的循环驱动练习，请参阅…… 斐波那契数列 Java， Java 回文程序，并 Bubbl排序算法 Java初学者如果需要复习一下如何声明flag和counter，应该阅读以下内容。 Java 变量 在主要 Java 教程.

常见问题