素数判定をJavaで書く．

素数判定をそこそこ高速にできたらいいなということで書いた．
何回も書くのがめんどそうなのでクラス化．
SPOJ 2 PRIME1 AC記念．

名前はPrimeGenになってるけど正確かどうかは気にしない．

static class PrimeGen {
	/**
         * 少なくともmまでの数字までが判定可能．
	 */
	public PrimeGen(int m) {
		m = (int) Math.sqrt(m);
		double max = 0;
		for (int i = 0,r=1; i < 4;r*=i) 
			max += r * m / Math.pow(Math.log1p(m), ++i);
		s = new int[(int) max]; // 素数の数を見積もる
		s[0] = 2;
		s[1] = 3;
		for (int i = 2, k = 1; i < s.length; ++k) {
			if (isPrime(6 * k - 1))
				s[i++] = 6 * k - 1;
			if (i < s.length && isPrime(6 * k + 1))
				s[i++] = 6 * k + 1;
		}
	}

	/**
         * nが素数かどうか判定．
	 */
	boolean isPrime(int n) {
		int m = (int) Math.sqrt(n);
		for (int i = 0; s[i] <= m; ++i) {
			int e = s[i];
			if (e > 0 && n != e && n % e < 1 || n < 2)
				return false;
		}
		return true;
	}

	/**
	 * 判定できる最大値
	 */
	int max() {
		return s[s.length - 1] * s[s.length - 1];
	}

	int next(int n) {
		int i = n + 1;
		for (; !isPrime(i); ++i);
		return i;
	}

	int prev(int n) {
		int i = n - 1;
		for (; !isPrime(i); --i);
		return i;
	}

	int[] s;
}

使い方(SPOJ 2 PRIME1)

PrimeGen pgen = new PrimeGen(1000000000);
for(int t=next();t-->0;){
    int s=next(),e=next();
    for(s=Math.max(2, s);s<=e;++s){
        if(pgen.isPrime(s)){
            System.out.println(s);
        }
    }
    System.out.println();
}