Java中的素数测试如何工作？ [英] How does this prime number test in Java work?

问题描述

下面的代码片段会检查给定的数字是否为素数。有人可以向我解释为什么这有效吗？这段代码是我们为Java考试提供的学习指南。

The code snippet below checks whether a given number is a prime number. Can someone explain to me why this works? This code was on a study guide given to us for a Java exam.

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

推荐答案

整体理论

条件 if（number％j == 0）询问 number 可以被整除_

素数的定义是

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

a number divisible by only itself and 1

所以如果你测试2和数字之间的所有数字，并且它们都不是完全可分的然后它是素数，否则它不是。

so if you test all numbers between 2 and number, and none of them are exactly divisible then it is a prime, otherwise it is not.

当然你实际上没有一直到数字，因为数字不能被半数以上的任何东西完全整除编号。

Of course you don't actually have to go all way to the number, because number cannot be exactly divisible by anything above half number.

这如果我们假设数字 = 12，那么它将通过增加j的值运行，然后它将运行 j = 2， 3,4,5,6

This section runs through values of increasing j, if we pretend that number = 12 then it will run through j = 2,3,4,5,6

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

如果声明

此部分将结果设置为1，如果在任何时候数字完全可被 j整除。一旦设置为1，结果永远不会重置为0.

If statement

This section sets result to 1, if at any point number is exactly divisible by j. result is never reset to 0 once it has been set to 1.

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

进一步改善

当然你可以进一步提高，因为你实际上需要不高于 sqrt（数字）但是这个片段决定不去做;你不需要更高的原因是因为如果（例如）40可以被4整除，则它是4 * 10，你不需要测试4和10.并且在那些对中，总是低于 sqrt（数字）。

Further improvements

Of course you can improve that even more because you actually need go no higher than sqrt(number) but this snippet has decided not to do that; the reason you need go no higher is because if (for example) 40 is exactly divisible by 4 it is 4*10, you don't need to test for both 4 and 10. And of those pairs one will always be below sqrt(number).

值得注意的是，他们似乎打算使用结果作为布尔值，但实际上使用整数0和1代表真和假。这不是一个好习惯。

It's also worth noting that they appear to have intended to use result as a boolean, but actually used integers 0 and 1 to represent true and false instead. This is not good practice.

这篇关于Java中的素数测试如何工作？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！