Java中的素数测试如何工作？

Question

下面的代码段检查给定数字是否为质数。有人可以向我解释为什么这行得通吗？该代码在为Java考试提供给我们的学习指南中。

public static void main(String[] args)
{    
    int j = 2;
    int result = 0;
    int number = 0;
    Scanner reader = new Scanner(System.in);
    System.out.println("Please enter a number: ");
    number = reader.nextInt();
    while (j <= number / 2)
    {
        if (number % j == 0)
        {
           result = 1;
        }
        j++;
    }
    if (result == 1)
    {
        System.out.println("Number: " + number + " is Not Prime.");
    }
    else
    {
        System.out.println("Number: " + number + " is Prime. ");
    }
}

Answer 1

整体理论

条件if (number % j == 0)询问是否可以number被整除j

素数的定义是

一个只能被自己和1整除的数字

因此，如果您测试2到number之间的所有数字，并且没有一个数字能被整除，则它是质数，否则就不是质数。

当然，您实际上不必一路前进number，因为number不能被一半以上的东西完全整除number。

具体章节

While循环

本节将通过增加j的值进行操作，如果我们假装number= 12，则它将通过j= 2,3,4,5,6

  int j = 2;
  .....
  while (j <= number / 2)
  {
      ........
      j++;
  }

如果陈述

result如果在任何点number都可被整除，则此部分设置为1 j。一旦设置为1，result就永远不会 复位 为0。

  ......
  if (number % j == 0)
  {
     result = 1;
  }
  .....

进一步改进

当然，您可以进一步提高它，因为您实际需要的不高于sqrt(number)此，但是此代码段决定不这样做。您不需要继续走高的原因是因为（例如）如果40可以被4整除，那么它就是4 * 10，则不需要测试4和10。并且在这对对中始终会在下面sqrt(number)。

还值得注意的是，它们似乎打算result用作布尔值，但实际上使用整数0和1来表示true和false。这不是一个好习惯。