素数判定 2007/09/15

pojでacceptされるためにはやいほうがよいようなので、ちょっと計測してみました。
マシンは、macbookでeclipse上での実行です。

calc:[2813]ms
BigInteger ver:[7337]ms
calc:[2790]ms
BigInteger ver:[7210]ms
same result?:true

わかりづらいですが、
calcのほうが自分で実装したもの、BigIntegerがisProbablePrimeメソッドを利用したものです。

数が大きい場合、
BigIntegerのisProbablePrimeを使用する場合、引数のcertaintyを少なくすると早くなるけど、精度が悪くなります。


コードは以下

package p2262;

import java.math.BigInteger;

public class Test2 {

public static void main(String[] args) {
int loop = 1000000;
a(loop);
b(loop);
a(loop);
b(loop);
System.out.println("same result?:" + checkLogic(loop));
}

static boolean checkLogic(int loop) {
for (int i = loop; 1 < i; i--) {
if (isPrime_1(i) != isPrime_2(i)) {
System.out.println("val:"+i);
return false;
}

}
return true;
}

static void a(int loop) {
long start = 0;
start = System.currentTimeMillis();
for (int i = 0; i < loop; i++) {
isPrime_2(i);

}
System.out.println("calc:[" + (System.currentTimeMillis() - start)
+ "]ms");
}

static void b(int loop) {
long start = 0;
start = System.currentTimeMillis();
for (int i = 0; i < loop; i++) {
isPrime_1(i);

}
System.out.println("BigInteger ver:["
+ (System.currentTimeMillis() - start) + "]ms");
}

static boolean isPrime_1(int p) {
return BigInteger.valueOf(p).isProbablePrime(10);
}

static boolean isPrime_2(int n) {
int i;
for (i = 2; i <= Math.sqrt(n); i++)
if (n % i == 0)
return false;
return true;
}

}