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.

具体部分

循环

这部分运行增加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代表真和假.这不是好习惯.

Answer 2

我试图评论每一行来解释正在进行的过程,希望它有所帮助!

int j = 2;   //variable
int result = 0; //variable
int number = 0; //variable
Scanner reader = new Scanner(System.in); //Scanner object
System.out.println("Please enter a number: "); //Instruction
number = reader.nextInt(); //Get the number entered
while (j <= number / 2) //start loop, during loop j will become each number between 2 and 
{                             //the entered number divided by 2
    if (number % j == 0) //If their is no remainder from your number divided by j...
    {
        result = 1;  //Then result is set to 1 as the number divides equally by another number, hergo
    }                //it is not a prime number
    j++;  //Increment j to the next number to test against the number you entered
}
if (result == 1)  //check the result from the loop
{
    System.out.println("Number: " + number + " is Not Prime."); //If result 1 then a prime   
}
else
{
    System.out.println("Number: " + number + " is Prime. "); //If result is not 1 it's not a prime
}