在 Java 中测试素性的最快方法是什么？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2385909/
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
What would be the fastest method to test for primality in Java?
提问by Anantha Kumaran
I am trying to find the fastest way to check whether a given number is prime or not (in Java). Below are several primality testing methods I came up with. Is there any better way than the second implementation(isPrime2)?
我试图找到检查给定数字是否为质数的最快方法（在 Java 中）。以下是我想出的几种素性测试方法。有没有比第二个实现（isPrime2）更好的方法？
public class Prime {
public static boolean isPrime1(int n) {
if (n <= 1) {
return false;
}
if (n == 2) {
return true;
}
for (int i = 2; i <= Math.sqrt(n) + 1; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
public static boolean isPrime2(int n) {
if (n <= 1) {
return false;
}
if (n == 2) {
return true;
}
if (n % 2 == 0) {
return false;
}
for (int i = 3; i <= Math.sqrt(n) + 1; i = i + 2) {
if (n % i == 0) {
return false;
}
}
return true;
}
}
public class PrimeTest {
public PrimeTest() {
}
@Test
public void testIsPrime() throws IllegalArgumentException, IllegalAccessException, InvocationTargetException {
Prime prime = new Prime();
TreeMap<Long, String> methodMap = new TreeMap<Long, String>();
for (Method method : Prime.class.getDeclaredMethods()) {
long startTime = System.currentTimeMillis();
int primeCount = 0;
for (int i = 0; i < 1000000; i++) {
if ((Boolean) method.invoke(prime, i)) {
primeCount++;
}
}
long endTime = System.currentTimeMillis();
Assert.assertEquals(method.getName() + " failed ", 78498, primeCount);
methodMap.put(endTime - startTime, method.getName());
}
for (Entry<Long, String> entry : methodMap.entrySet()) {
System.out.println(entry.getValue() + " " + entry.getKey() + " Milli seconds ");
}
}
}
采纳答案by Bart Kiers
Here's another way:
这是另一种方式：
boolean isPrime(long n) {
if(n < 2) return false;
if(n == 2 || n == 3) return true;
if(n%2 == 0 || n%3 == 0) return false;
long sqrtN = (long)Math.sqrt(n)+1;
for(long i = 6L; i <= sqrtN; i += 6) {
if(n%(i-1) == 0 || n%(i+1) == 0) return false;
}
return true;
}
and BigInteger's isProbablePrime(...)is valid for all 32 bit int's.
并且BigInteger's isProbablePrime(...)对所有 32 位都有效int。
EDIT
编辑
Note that isProbablePrime(certainty)does not always produce the correct answer. When the certainty is on the low side, it produces false positives, as @dimo414 mentioned in the comments.
请注意，isProbablePrime(certainty)这并不总是会产生正确的答案。当确定性偏低时，它会产生误报，正如评论中提到的@dimo414。
Unfortunately, I could not find the source that claimed isProbablePrime(certainty)is valid for all (32-bit) int's (given enough certainty!).
不幸的是，我找不到声称isProbablePrime(certainty)对所有 (32-bit) 都有效的来源int（如果有足够的确定性！）。
So I performed a couple of tests. I created a BitSetof size Integer.MAX_VALUE/2representing all uneven numbers and used a prime sieve to find all primes in the range 1..Integer.MAX_VALUE. I then looped from i=1..Integer.MAX_VALUEto test that every new BigInteger(String.valueOf(i)).isProbablePrime(certainty) == isPrime(i).
所以我进行了几次测试。我创建了一个代表所有奇数BitSet的大小，Integer.MAX_VALUE/2并使用素数筛来查找范围内的所有素数1..Integer.MAX_VALUE。然后我循环i=1..Integer.MAX_VALUE测试每个new BigInteger(String.valueOf(i)).isProbablePrime(certainty) == isPrime(i).
For certainty 5 and 10, isProbablePrime(...)produced false positives along the line. But with isProbablePrime(15), no test failed.
对于确定性 5 和 10，isProbablePrime(...)沿线产生了误报。但是isProbablePrime(15)，没有测试失败。
Here's my test rig:
这是我的测试设备：
import java.math.BigInteger;
import java.util.BitSet;
public class Main {
static BitSet primes;
static boolean isPrime(int p) {
return p > 0 && (p == 2 || (p%2 != 0 && primes.get(p/2)));
}
static void generatePrimesUpTo(int n) {
primes = new BitSet(n/2);
for(int i = 0; i < primes.size(); i++) {
primes.set(i, true);
}
primes.set(0, false);
int stop = (int)Math.sqrt(n) + 1;
int percentageDone = 0, previousPercentageDone = 0;
System.out.println("generating primes...");
long start = System.currentTimeMillis();
for(int i = 0; i <= stop; i++) {
previousPercentageDone = percentageDone;
percentageDone = (int)((i + 1.0) / (stop / 100.0));
if(percentageDone <= 100 && percentageDone != previousPercentageDone) {
System.out.println(percentageDone + "%");
}
if(primes.get(i)) {
int number = (i * 2) + 1;
for(int p = number * 2; p < n; p += number) {
if(p < 0) break; // overflow
if(p%2 == 0) continue;
primes.set(p/2, false);
}
}
}
long elapsed = System.currentTimeMillis() - start;
System.out.println("finished generating primes ~" + (elapsed/1000) + " seconds");
}
private static void test(final int certainty, final int n) {
int percentageDone = 0, previousPercentageDone = 0;
long start = System.currentTimeMillis();
System.out.println("testing isProbablePrime(" + certainty + ") from 1 to " + n);
for(int i = 1; i < n; i++) {
previousPercentageDone = percentageDone;
percentageDone = (int)((i + 1.0) / (n / 100.0));
if(percentageDone <= 100 && percentageDone != previousPercentageDone) {
System.out.println(percentageDone + "%");
}
BigInteger bigInt = new BigInteger(String.valueOf(i));
boolean bigIntSays = bigInt.isProbablePrime(certainty);
if(isPrime(i) != bigIntSays) {
System.out.println("ERROR: isProbablePrime(" + certainty + ") returns "
+ bigIntSays + " for i=" + i + " while it " + (isPrime(i) ? "is" : "isn't" ) +
" a prime");
return;
}
}
long elapsed = System.currentTimeMillis() - start;
System.out.println("finished testing in ~" + ((elapsed/1000)/60) +
" minutes, no false positive or false negative found for isProbablePrime(" + certainty + ")");
}
public static void main(String[] args) {
int certainty = Integer.parseInt(args[0]);
int n = Integer.MAX_VALUE;
generatePrimesUpTo(n);
test(certainty, n);
}
}
which I ran by doing:
我通过以下方式运行：
java -Xmx1024m -cp . Main 15
The generating of the primes took ~30 sec on my machine. And the actual test of all iin 1..Integer.MAX_VALUEtook around 2 hours and 15 minutes.
在我的机器上生成素数大约需要 30 秒。而所有的实际测试i中1..Integer.MAX_VALUE花了大约2小时15分钟。
回答by Jimmy
You took the first step in eliminating all multiples of 2.
您迈出了消除所有 2 的倍数的第一步。
However, why did you stop there? you could have eliminated all multiples of 3 except for 3, all multiples of 5 except for 5, etc.
然而，你为什么停在那里？您可以消除除 3 以外的所有 3 的倍数、除 5 以外的所有 5 的倍数，等等。
When you follow this reasoning to its conclusion, you get the Sieve of Eratosthenes.
回答by Kannan Ekanath
What you have written is what most common programmers do and which should be sufficient most of the time.
您所写的是大多数普通程序员所做的，并且在大多数情况下应该足够了。
However, if you are after the "best scientific algorithm" there are many variations (with varying levels of certainty) documented http://en.wikipedia.org/wiki/Prime_number.
但是，如果您追求“最佳科学算法”，那么http://en.wikipedia.org/wiki/Prime_number记录了许多变体（具有不同程度的确定性）。
For example, if you have a 70 digit number JVM's physical limitations can prevent your code from running in which case you can use "Sieves" etc.
例如，如果您有一个 70 位数字，JVM 的物理限制会阻止您的代码运行，在这种情况下，您可以使用“筛子”等。
Again, like I said if this was a programming question or a general question of usage in software your code should be perfect :)
再一次，就像我说的，如果这是一个编程问题或软件使用的一般问题，你的代码应该是完美的:)
回答by kgiannakakis
Your algorithm will work well for reasonably small numbers. For big numbers, advanced algorithms should be used (based for example on elliptic curves). Another idea will be to use some "pseuso-primes" test. These will test quickly that a number is a prime, but they aren't 100% accurate. However, they can help you rule out some numbers quicker than with your algorithm.
您的算法适用于相当小的数字。对于大数字，应使用高级算法（例如基于椭圆曲线）。另一个想法是使用一些“伪素数”测试。这些将快速测试一个数字是素数，但它们不是 100% 准确。但是，与您的算法相比，它们可以帮助您更快地排除一些数字。
Finally, although the compiler will probably optimise this for you, you should write:
最后，虽然编译器可能会为你优化它，你应该写：
int max = (int) (Math.sqrt(n) + 1);
for (int i = 3; i <= max; i = i + 2) {
}
回答by saugata
If you are just trying to find if a number is prime or not it's good enough, but if you're trying to find all primes from 0 to n a better option will be the Sieve of Eratosthenes
如果你只是想找出一个数是否是素数，那就足够了，但如果你想找出从 0 到 na 的所有素数，更好的选择将是埃拉托色尼筛
But it will depend on limitations of java on array sizes etc.
但这将取决于 java 对数组大小等的限制。
回答by Aurril
Dependent on the length of the number you need to test you could precompute a list of prime numbers for small values (n < 10^6), which is used first, if the asked number is within this range. This is of course the fastest way. Like mentioned in other answers the Sieve of Eratosthenesis the preferred method to generate such a precomputed list.
根据您需要测试的数字的长度，您可以预先计算小值 (n < 10^6) 的素数列表，如果询问的数字在此范围内，则首先使用该列表。这当然是最快的方式。就像其他答案中提到的那样，Eratosthenes的筛选是生成此类预先计算列表的首选方法。
If your numbers are larger than this, you can use the primality test of Rabin. Rabin primality test
如果你的数字大于这个，你可以使用 Rabin 的素性测试。 拉宾素性检验
回答by Brandon E Taylor
Take a look at the AKS primality test(and its various optimizations). It is a deterministic primality test that runs in polynomial time.
看看AKS 素性测试（及其各种优化）。它是在多项式时间内运行的确定性素性测试。
There is an implementation of the algorithm in Java from the University of Tuebingen (Germany) here
图宾根大学（德国）这里有一个 Java 算法的实现
回答by user102008
This is the most elegant way:
这是最优雅的方式：
public static boolean isPrime(int n) {
return !new String(new char[n]).matches(".?|(..+?)\1+");
}
Java 1.4+. No imports needed.
Java 1.4+。不需要进口。
So short. So beautiful.
这么短。如此美丽。
回答by Ariful Islam
i think this method is best. at least for me-
我认为这个方法是最好的。至少对于我来说-
public static boolean isPrime(int num)
{
for (int i = 2; i<= num/i; i++)
{
if (num % i == 0)
{
return false;
}
}
return num > 1;
}
回答by Nilesh Patil
Algorithm Efficiency : O( n^(1/2)) Algorithm
算法效率：O(n^(1/2)) 算法
Note: This sample code below contains count variables and calls to a print function for the purposes of printing the results :
注意：下面的示例代码包含计数变量并调用打印函数以打印结果：
import java.util.*;
class Primality{
private static void printStats(int count, int n, boolean isPrime) {
System.err.println( "Performed " + count + " checks, determined " + n
+ ( (isPrime) ? " is PRIME." : " is NOT PRIME." ) );
}
/**
* Improved O( n^(1/2)) ) Algorithm
* Checks if n is divisible by 2 or any odd number from 3 to sqrt(n).
* The only way to improve on this is to check if n is divisible by
* all KNOWN PRIMES from 2 to sqrt(n).
*
* @param n An integer to be checked for primality.
* @return true if n is prime, false if n is not prime.
**/
public static boolean primeBest(int n){
int count = 0;
// check lower boundaries on primality
if( n == 2 ){
printStats(++count, n, true);
return true;
} // 1 is not prime, even numbers > 2 are not prime
else if( n == 1 || (n & 1) == 0){
printStats(++count, n, false);
return false;
}
double sqrtN = Math.sqrt(n);
// Check for primality using odd numbers from 3 to sqrt(n)
for(int i = 3; i <= sqrtN; i += 2){
count++;
// n is not prime if it is evenly divisible by some 'i' in this range
if( n % i == 0 ){
printStats(++count, n, false);
return false;
}
}
// n is prime
printStats(++count, n, true);
return true;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
while(scan.hasNext()) {
int n = scan.nextInt();
primeBest(n);
System.out.println();
}
scan.close();
}
}
When the prime number 2147483647 is entered, it produces the following output:
当输入质数 2147483647 时，它会产生以下输出：
Performed 23170 checks, determined 2147483647 is PRIME.
执行了 23170 次检查，确定 2147483647 是 PRIME。
