import java.math.BigInteger; import java.util.BitSet; public class sprpLiars { private static final int maxPrime = Integer.MAX_VALUE; private static final BitSet initBasePrimes(int max) { BitSet primes = new BitSet(max / 2 + 4); for (long i=3; i*i<=max; i+=2) { if (!primes.get((int)i>>1)) { for (long j=i*i; j<=max; j+=i<<1) { primes.set((int)j>>1); } } } primes.flip(0, max>>1); return primes; } public static final long modPow(long i, long j, long k) { if(k > Integer.MAX_VALUE) { BigInteger x=BigInteger.valueOf(i); BigInteger y=BigInteger.valueOf(j); BigInteger z=BigInteger.valueOf(k); return x.modPow(y,z).longValue(); } i%=k; if(j == 2) return i*i%k; long val=1; while (j>0){ if((j&1)!=0) val=val*i%k; i=i*i%k; j>>=1; } return val; } private static final boolean miller_rabin(long n, long[] bases) { int s=0; long d=n-1; while ((d&1)==0) { s++; d>>=1; } LOOP: for(long a : bases) { long x = modPow(a,d,n); if (x==1 || x==n-1) continue LOOP; for (int r=0; r Integer.MAX_VALUE ? modPow(x,2,n) : x*x%n; if (x==1) return false; else if (x==n-1) continue LOOP; } return false; } return true; } public static void main(String[] args) { BitSet primes = initBasePrimes(maxPrime); System.out.println("Sieving done"); long[] bases = {11000544, 31481107}; for(long i = 5; i < maxPrime; i+=2) if(!primes.get((int)i>>1) && miller_rabin(i, bases)) System.out.println(i); } }