Prime - nise-nabe/topcoder GitHub Wiki

static class Prime {
	/**
         * 少なくともmまでの数字までが判定可能．
	 */
	public Prime(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;
}

How To Use

2. Prime Generator

Prime pgen = new Prime(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();
}