什么是测试的素数在Java中最快的方法是什么？ [英] What would be the fastest method to test for primality in Java?
问题描述
我想找到检查一个给定数是否是素数还是没有（在Java中）的最快方法。下面是我想出了几种素性测试方法。有没有什么比第二个实现（isPrime2）？更好的办法
公共类总理{
公共静态布尔isPrime1（INT N）{
如果（正＆其中; = 1）{
返回false;
}
如果（N == 2）{
返回true;
}
的for（int i = 2; I＆LT; =的Math.sqrt（N）+ 1;我++）{
如果（N％我== 0）{
返回false;
}
}
返回true;
}
公共静态布尔isPrime2（INT N）{
如果（正＆其中; = 1）{
返回false;
}
如果（N == 2）{
返回true;
}
如果（N％2 == 0）{
返回false;
}
的for（int i = 3; I＆LT; =的Math.sqrt（N）+ 1; i = i + 2）{
如果（N％我== 0）{
返回false;
}
}
返回true;
}
}
公共类PrimeTest {
公共PrimeTest（）{
}
@测试
公共无效testIsPrime（）抛出：IllegalArgumentException - ，IllegalAccessException，的InvocationTargetException {
总理素=新总理（）;
TreeMap的＆LT;长，字符串＆GT; methodMap =新TreeMap的＆LT;长，字符串＆GT;（）;
对于（方法方法：Prime.class.getDeclaredMethods（））{
长的startTime = System.currentTimeMillis的（）;
INT primeCount = 0;
的for（int i = 0; I＆LT; 1000000;我++）{
如果（（布尔）method.invoke（素，I））{
primeCount ++;
}
}
长endTime的= System.currentTimeMillis的（）;
Assert.assertEquals（method.getName（）+失败，78498，primeCount）;
methodMap.put（endTime的 - 的startTime，method.getName（））;
}
对于（进入＆LT;长，字符串＆GT;输入：methodMap.entrySet（））{
的System.out.println（entry.getValue（）++ entry.getKey（）+毫秒数）;
}
}
}
下面是另一种方式：
布尔isPrime（N久）{
如果（N 2）返回false;
如果（N = = 2 ||ñ== 3）返回true;
如果（N％2 == 0 || N％3 == 0）返回false;
长sqrtN =（长）的Math.sqrt（N）+1;
为（长I = 6L; I＆LT; = sqrtN; I + = 6）{
如果（正％第（i-1）== 0 || N％第（i + 1）== 0）返回false;
}
返回true;
}
和<一href="http://java.sun.com/javase/6/docs/api/java/math/BigInteger.html#isProbablePrime%28int%29"><$c$c>BigInteger's isProbablePrime（...） 是适用于所有32位 INT 的。
修改
注意 isProbablePrime（确定性）并不一定能得到正确的答案。当可以肯定的是偏低的，它会产生误报，如@ dimo414在评论中提到的。
不幸的是，我无法找到索赔的源 isProbablePrime（确定性）适用于所有（32位） INT 的（给予足够的肯定！）。
于是我进行了几个测试。我创建了一个位集合尺寸为Integer.MAX_VALUE / 2 重presenting所有不均匀数量和使用的首要筛找到所有素数的范围 1..Integer.MAX_VALUE 。我再从环 I = 1..Integer.MAX_VALUE 来测试每个新的BigInteger（将String.valueOf（I））。isProbablePrime（确定性） == isPrime（我）。
有关确定性5和10， isProbablePrime（...）生产线沿线误报。但随着 isProbablePrime（15），没有测试失败。
下面是我的试验台：
导入java.math.BigInteger的;
进口java.util.BitSet中;
公共类主要{
静态位集合的素数;
静态布尔isPrime（INT P）{
回到P＆GT; 0安培;＆安培; （第== 2 ||（第％2 = 0＆安培;！＆安培; primes.get（π/ 2）））;
}
静态无效generatePrimesUpTo（INT N）{
素数=新位集合（N / 2）;
的for（int i = 0; I＆LT; primes.size（）;我++）{
primes.set（我，真正的）;
}
primes.set（0，假）;
INT停止=（INT）的Math.sqrt（N）+ 1;
INT percentageDone = 0，previousPercentageDone = 0;
的System.out.println（生成素数...）;
长时间启动= System.currentTimeMillis的（）;
的for（int i = 0; I＆LT; =停止;我++）{
previousPercentageDone = percentageDone;
percentageDone =（INT）（（1 + 1.0）/（停止/ 100.0））;
如果（percentageDone＆LT; = 100安培;＆安培;！percentageDone = previousPercentageDone）{
的System.out.println（percentageDone +％）;
}
如果（primes.get（i））的{
INT数=（I * 2）+ 1;
为（中间体p值=编号* 2; P＆n种; P + =号）{
如果（对℃的）中断; // 溢出
如果（P％2 == 0）继续;
primes.set（P / 2，假）;
}
}
}
经过长= System.currentTimeMillis的（） - 启动;
的System.out.println（说完生成素〜+（已过/ 1000）+秒）;
}
私有静态无效测试（最终诠释确定性，最终诠释N）{
INT percentageDone = 0，previousPercentageDone = 0;
长时间启动= System.currentTimeMillis的（）;
的System.out.println（从1），测试isProbablePrime（+确定+ + N）;
的for（int i = 1;我n种;我++）{
previousPercentageDone = percentageDone;
percentageDone =（INT）（（1 + 1.0）/（N / 100.0））;
如果（percentageDone＆LT; = 100安培;＆安培;！percentageDone = previousPercentageDone）{
的System.out.println（percentageDone +％）;
}
BigInteger的BIGINT =新的BigInteger（将String.valueOf（一））;
布尔bigIntSays = bigInt.isProbablePrime（确定性）;
如果（isPrime（ⅰ）！= bigIntSays）{
的System.out.println（ERROR：isProbablePrime（+确定+）返回
+ bigIntSays +对于i =+ 1 +，同时+（isPrime（我）是：是不是）+
素）;
返回;
}
}
经过长= System.currentTimeMillis的（） - 启动;
+（（已过/ 1000）/ 60）+的System.out.println（在〜成品检验
分钟，无假阳性或假阴性匹配isProbablePrime（+确定性+））;
}
公共静态无效的主要（字串[] args）{
INT确定性=的Integer.parseInt（参数[0]）;
INT N = Integer.MAX_VALUE的;
generatePrimesUpTo（N）;
测试（确定性，N）;
}
}
这是我跑这样做：
的java -Xmx1024m -cp。主15
素数的产生了约30秒在我的机器上。和所有的我在 1..Integer.MAX_VALUE 花了约2小时15分钟的实际测试。
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 ");
}
}
}
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.
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.
Unfortunately, I could not find the source that claimed isProbablePrime(certainty) is valid for all (32-bit) int's (given enough certainty!).
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).
For certainty 5 and 10, isProbablePrime(...) produced false positives along the line. But with isProbablePrime(15), no test failed.
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 i in 1..Integer.MAX_VALUE took around 2 hours and 15 minutes.
这篇关于什么是测试的素数在Java中最快的方法是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
