ミラー-ラビン素数判定法 - Wikipedia
http://ja.wikipedia.org/wiki/%E3%83%9F%E3%83%A9%E3%83%BC-%E3%83%A9%E3%83%93%E3%83%B3%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A%E6%B3%95

少なくとも5桁くらいまでの整数は正確に判定できると思います。

MillerRabinTest.java

// Miller-Rabin素数判定クラス
class MillerRabinTest{

	// nが素数ならtrue、nが合成数ならfalseを返す
	// kは判定サイクル数で、kが大きいほど素数判定が正確になり、速度は低下する。
	public static boolean isPrime(int n, int k) {
		// 2は素数
		if (n == 2) {
			return true;
		}
		// 1は素数ではない
		// 2以外の偶数は素数ではない
		if (n == 1 || n % 2 == 0) {
			return false;
		}
		// n-1を2のべき乗で割って2^s*dの形式に変形
		int d = n - 1;
		int s = 0;
		while (d % 2 == 0) {
			d = d / 2;
			s++;
		}
		// 判定サイクル
		for (int i = 0; i < k; i++) {
			boolean isPP = false;
			// 1からn-1の範囲から整数aをランダムに選ぶ
			int a = (int) (Math.round((n - 2) * Math.random()) + 1);
			// a^d mod n が1もしくはn-1なら、nはprobably prime
			int r = modPow(a, d, n);
			if (r == 1 || r == n - 1) {
				isPP = true;
			}
			// r^2 mod n が-1なら、nはprobably prime
			for (int j = 0; j < s; j++) {
				r = modPow(r, 2, n);
				if (r == n - 1) {
					isPP = true;
				}
			}
			// 上記のどちらにも当てはまらない場合、nはcomposite
			if (!isPP) {
				return false;
			}
		}
		return true;
	}
	
	// べき剰余の計算
	private static int modPow(long x, int k, int m) {
		if (k == 0) {
			return 1;
		}
		if (k % 2 == 0) {
			return modPow(x * x % m, k / 2, m);
		} else {
			return (int) (modPow(x, k - 1, m) * x % m);
		}
	}
}