在 Java 中测试素性的最快方法是什么? [英] What would be the fastest method to test for primality in Java?
问题描述
我试图找到检查给定数字是否为质数的最快方法(在 Java 中).以下是我想出的几种素性测试方法.有没有比第二种实现(isPrime2)更好的方法?
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)?
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 ");
}
}
}
推荐答案
这是另一种方式:
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;
}
和 BigInteger 的 isProbablePrime(...)
对所有 32 位 int
都有效.
编辑
请注意,isProbablePrime(certainty)
并不总是产生正确的答案.当确定性偏低时,就会产生误报,正如评论中提到的@dimo414.
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)
对所有(32 位)int
有效的来源(如果有足够的确定性!).
Unfortunately, I could not find the source that claimed isProbablePrime(certainty)
is valid for all (32-bit) int
's (given enough certainty!).
所以我进行了几次测试.我创建了一个大小为 Integer.MAX_VALUE/2
的 BitSet
表示所有奇数,并使用素数筛来查找 1..Integer.MAX_VALUE 范围内的所有素数代码>.然后我从
i=1..Integer.MAX_VALUE
循环来测试每个 new BigInteger(String.valueOf(i)).isProbablePrime(certainty) == isPrime(i)
.
So I performed a couple of tests. I created a BitSet
of size Integer.MAX_VALUE/2
representing 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_VALUE
to test that every new BigInteger(String.valueOf(i)).isProbablePrime(certainty) == isPrime(i)
.
对于确定性 5 和 10,isProbablePrime(...)
沿线产生了误报.但是使用 isProbablePrime(15)
,没有测试失败.
For certainty 5 and 10, isProbablePrime(...)
produced false positives along the line. But with isProbablePrime(15)
, no test failed.
这是我的测试设备:
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);
}
}
我是这样做的:
java -Xmx1024m -cp . Main 15
在我的机器上生成素数需要大约 30 秒.而1..Integer.MAX_VALUE
中所有i
的实际测试耗时约2小时15分钟.
The generating of the primes took ~30 sec on my machine. And the actual test of all i
in 1..Integer.MAX_VALUE
took around 2 hours and 15 minutes.
这篇关于在 Java 中测试素性的最快方法是什么?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!