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

- Adam Staples

---

你没明白在哪里？ - Suresh Atta

素数的定义是只能被 1 和它本身整除的数字。 - Richard Tingle

你不理解的部分是什么？我需要确切地知道要解释什么。 - Lukas Warsitz

为什么它会不起作用？ - Simon Forsberg

@AdamStaples 哇，你连代码都看不懂。"如果那个模数等于1"？它检查的是模数是否等于0，也就是j能否整除这个数字。 - Kayaman

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++;
  }

条件语句

如果number能够被j整除，此部分将把result设置为1。一旦result被设置为1，它就不会再被重置为0。

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

进一步的改进

当然，你可以进一步改进它，因为实际上你只需要检测到 sqrt(number) 就足够了。但是这段代码没有这样做的原因是，例如如果 40 可以被 4 整除，那么它就是 4*10，你不需要同时测试 4 和 10。而其中一个值将始终低于 sqrt(number)。

值得注意的是，他们似乎打算使用 result 作为布尔类型，但实际上使用整数 0 和 1 代表 true 和 false。这不是好的编程习惯。

- Richard Tingle

---

好的，我不明白为什么在j等于2时要对数字取模。它应该对数字取模以查看它是否可以被自身和1整除吗？ - Adam Staples

@AdamStaples j++; 会增加j的值，循环将在2、3、4、5、6、……number/2-1、number/2测试j。 - Richard Tingle

@AdamStaples 我添加了一个关于 while 循环正在做什么的部分。 - Richard Tingle

哦，现在我感觉自己像个白痴。因为这是一个while循环，它会迭代所有的选择，直到while循环的布尔值为“true”。由于它只检查数字/2次，它永远不会达到j = number，因此如果是质数，它永远不会与j模0同余，因此也永远不等于“1”。好吧，我不知道我是否讲清楚了，但我完全明白为什么它有效。好的，谢谢！ - Adam Staples

@AdamStaples 很棒，很高兴能帮忙。Java很难入门，但一旦掌握就非常好。 - Richard Tingle

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
}    

- Levenal

---

如果你在代码之外用简单的英语解释一下，这个答案可以大大改进。 - user456814

Answer 3

Java中的java.math.BigInteger类包含一个方法isProbablePrime(int certainty)，用于检查数字的素性。

isProbablePrime(int certainty)：BigInteger类中的一个方法，用于检查给定的数字是否为素数。 当certainty = 1时，如果BigInteger是素数，则返回true，如果BigInteger是合数，则返回false。

在该方法中使用Miller-Rabin素性测试算法来检查素性。

import java.math.BigInteger;

public class TestPrime {

    public static void main(String[] args) {
        int number = 83;
        boolean isPrime = testPrime(number);
        System.out.println(number + " is prime : " + isPrime);

    }

    /**
     * method to test primality
     * @param number
     * @return boolean
     */
    private static boolean testPrime(int number) {
        BigInteger bValue = BigInteger.valueOf(number);

        /**
         * isProbablePrime method used to check primality. 
         * */
        boolean result = bValue.isProbablePrime(1);

        return result;
    }
}

输出: 83是质数 : 真

更多信息请参见我的博客.

- Rajesh Dixit

Answer 4

它的工作原理是逐个迭代2到输入数的一半之间的所有数字（因为任何大于输入数/ 2但小于输入数的数字都会产生分数）。 如果输入数除以 j 的余数为0（if（number％j == 0）），则输入数可被除1或本身以外的数字整除。在这种情况下，结果设置为1，该数字不是质数。

- Chris Knight

Answer 5

请尝试

public class PalindromePrime   {
     private static int g ,k ,n =0,i,m ; 

     static String b ="";
    private static Scanner scanner = new Scanner( System.in );

    public static void main(String [] args) throws IOException {

        System.out.print(" Please Inter Data : "); 
        g = scanner.nextInt();  

        System.out.print(" Please Inter Data 2  : "); 
        m = scanner.nextInt();

        count(g,m);


        }

//      
        //********************************************************************************    


    private static    int count(int L, int R) 

        for( i= L ; i<= R ;i++){
            int count = 0 ;
            for( n = i ; n >=1 ;n -- ){

                if(i%n==0){

                    count = count + 1 ;
                }           
            }
            if(count == 2)
            {       
                b = b +i + "" ; 
            }   

        }

        System.out.print("  Data  : "); 
        System.out.print("  Data : \n "  +b );  

        return R;

        }
} 

- Pong Petrung