Java 中的这个质数测试是如何工作的？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/19514680/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How does this prime number test in Java work?
提问by Adam Staples
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.
下面的代码片段检查给定的数字是否是素数。有人可以向我解释为什么这有效吗？这段代码位于我们为 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. ");
}
}
采纳答案by Richard Tingle
Overall theory
整体理论
The condition if (number % j == 0)asks if numberis exactly divisible by j
条件if (number % j == 0)询问是否可以number被精确整除j
The definition of a prime is
素数的定义是
a number divisible by only itself and 1
一个只能被它自己和 1 整除的数
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.
因此，如果您测试 2 和 number 之间的所有数字，并且它们都不能完全整除，则它是素数，否则不是。
Of course you don't actually have to go all way to the number, because numbercannot be exactly divisible by anything above half number.
当然，您实际上不必一直走到number，因为number不能被任何高于 half 的东西整除number。
Specific sections
具体部分
While loop
while 循环
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
本节通过增加 j 的值，如果我们假设number= 12 那么它将通过j= 2,3,4,5,6
int j = 2;
.....
while (j <= number / 2)
{
........
j++;
}
If statement
如果语句
This section sets resultto 1, if at any point numberis exactly divisible by j. resultis never resetto 0 once it has been set to 1.
result如果在任何时候可以number被 整除，则此部分设置为 1 j。一旦设置为 1，result就永远不会重置为 0。
......
if (number % j == 0)
{
result = 1;
}
.....
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).
当然，您可以进一步改进它，因为您实际上不需要更高，sqrt(number)但是此代码段已决定不这样做；你不需要更高的原因是因为如果（例如）40 可以被 4 整除它是 4*10，你不需要测试 4 和 10。而这些对中的一个总是低于sqrt(number)。
It's also worth noting that they appear to have intended to use resultas a boolean, but actually used integers 0 and 1 to represent true and false instead. This is not good practice.
还值得注意的是，它们似乎打算result用作布尔值，但实际上使用整数 0 和 1 来表示真假。这不是好的做法。
回答by Chris Knight
It works by iterating over all number between 2 and half of the number entered (since any number greater than the input/2 (but less than the input) would yield a fraction). If the number input divided by jyields a 0 remainder (if (number % j == 0)) then the number input isdivisible by a number other than 1 or itself. In this case result is set to 1 and the number is not a prime number.
它的工作原理是遍历输入数字的 2 到一半之间的所有数字（因为任何大于输入/2（但小于输入）的数字都会产生一个分数）。如果数字输入除以j产率一个0余数（if (number % j == 0)），则号码输入是由超过1或本身以外的数整除。在这种情况下，结果设置为 1，并且该数字不是素数。
回答by Levenal
I've tried to comment each line to explain the processes going on, hope it helps!
我试图评论每一行来解释正在进行的过程，希望它有所帮助！
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
}
回答by Pong Petrung
Do try
尝试
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;
}
}
回答by Rajesh Dixit
Java java.math.BigInteger class contains a method isProbablePrime(int certainty)to check the primality of a number.
Java java.math.BigInteger 类包含一个方法isProbablePrime(int specificity)来检查数字的素数。
isProbablePrime(int certainty): A method in BigIntegerclass to check if a given number is prime.
For certainty = 1, it return true if BigIntegeris prime and false if BigIntegeris composite.
isProbablePrime(int certainty)：BigInteger类中用于检查给定数字是否为素数的方法。对于certainty = 1，如果BigInteger是素数则返回真，如果BigInteger是复合则返回假。
Miller–Rabin primality algorithm is used to check primality in this method.
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;
}
}
Output: 83 is prime : true
Output: 83 is prime : true
For more information, see my blog.
有关更多信息，请参阅我的博客。
