import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

/** Five ways to test primality, plus "print primes in a range". */
public class PrimeNumbers {

    // BEGIN naive
    static boolean isPrimeNaive(int n) {
        if (n < 2) return false;
        for (int i = 2; i < n; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
    // END naive

    // BEGIN sqrt
    static boolean isPrimeSqrt(int n) {
        if (n < 2) return false;
        for (long i = 2; i * i <= n; i++) {          // long: i * i would overflow int near 2^31
            if (n % i == 0) return false;
        }
        return true;
    }
    // END sqrt

    // BEGIN sixk
    static boolean isPrime6k(int n) {
        if (n < 2) return false;
        if (n < 4) return true;                      // 2 and 3
        if (n % 2 == 0 || n % 3 == 0) return false;
        for (long i = 5; i * i <= n; i += 6) {       // every prime > 3 is 6k-1 or 6k+1
            if (n % i == 0 || n % (i + 2) == 0) return false;
        }
        return true;
    }
    // END sixk

    // BEGIN sieve
    static boolean[] sieve(int limit) {
        boolean[] composite = new boolean[limit + 1];
        for (int p = 2; (long) p * p <= limit; p++) {
            if (!composite[p]) {
                for (int m = p * p; m <= limit; m += p) composite[m] = true;
            }
        }
        return composite;                            // composite[i] == false and i >= 2  =>  prime
    }
    // END sieve

    // BEGIN bigint
    static boolean isPrimeBig(long n) {
        return BigInteger.valueOf(n).isProbablePrime(20);   // error chance below 2^-20
    }
    // END bigint

    // BEGIN range
    static List<Integer> primesInRange(int from, int to) {
        boolean[] composite = sieve(to);
        List<Integer> out = new ArrayList<>();
        for (int i = Math.max(2, from); i <= to; i++) {
            if (!composite[i]) out.add(i);
        }
        return out;
    }
    // END range

    static long timeMs(Runnable r) {
        long t = System.nanoTime();
        r.run();
        return (System.nanoTime() - t) / 1_000_000;
    }

    static int sink;

    public static void main(String[] args) {
        int[] tests = {0, 1, 2, 3, 4, 17, 25, 97, 100, 7919, 1_000_000_007};
        System.out.printf("%-12s %-6s %-6s %-6s %-6s %-6s%n", "n", "naive", "sqrt", "6k+-1", "sieve", "BigInt");
        for (int n : tests) {
            boolean[] comp = n >= 2 ? sieve(Math.min(n, 2_000_000)) : null;
            String sv = n > 2_000_000 ? "-" : String.valueOf(n >= 2 && !comp[n]);
            String nv = n > 100_000_000 ? "-" : String.valueOf(isPrimeNaive(n));
            System.out.printf("%-12d %-6s %-6s %-6s %-6s %-6s%n", n, nv, isPrimeSqrt(n), isPrime6k(n), sv, isPrimeBig(n));
        }

        System.out.println();
        System.out.println("Primes in [10, 50]: " + primesInRange(10, 50));

        // warm up the JIT so the first method measured is not penalised
        for (int i = 0; i < 3; i++) { sink += countNaive(20_000) + countSqrt(20_000) + count6k(20_000); }

        System.out.println();
        System.out.println("Count primes below 100,000 (answer: " + countSqrt(100_000) + ")");
        System.out.println("  naive : " + timeMs(() -> sink += countNaive(100_000)) + " ms");
        System.out.println("  sqrt  : " + timeMs(() -> sink += countSqrt(100_000)) + " ms");
        System.out.println("  6k+-1 : " + timeMs(() -> sink += count6k(100_000)) + " ms");
        System.out.println("  sieve : " + timeMs(() -> sink += countSieve(100_000)) + " ms");
        System.out.println("  BigInt: " + timeMs(() -> sink += countBig(100_000)) + " ms");

        System.out.println();
        System.out.println("Count primes below 10,000,000 (answer: " + countSieve(10_000_000) + ")");
        System.out.println("  sqrt  : " + timeMs(() -> sink += countSqrt(10_000_000)) + " ms");
        System.out.println("  6k+-1 : " + timeMs(() -> sink += count6k(10_000_000)) + " ms");
        System.out.println("  sieve : " + timeMs(() -> sink += countSieve(10_000_000)) + " ms");
        System.out.println("  BigInt: " + timeMs(() -> sink += countBig(10_000_000)) + " ms");

        System.out.println();
        System.out.println("One test of 1,000,000,007 (prime):");
        System.out.println("  naive : " + timeMs(() -> sink += isPrimeNaive(1_000_000_007) ? 1 : 0) + " ms");
        System.out.println("  sqrt  : " + timeMs(() -> sink += isPrimeSqrt(1_000_000_007) ? 1 : 0) + " ms");
        System.out.println("  6k+-1 : " + timeMs(() -> sink += isPrime6k(1_000_000_007) ? 1 : 0) + " ms");
        System.out.println("  BigInt: " + timeMs(() -> sink += isPrimeBig(1_000_000_007L) ? 1 : 0) + " ms");
        System.out.println("2^61-1 (Mersenne prime) via BigInteger: " + isPrimeBig((1L << 61) - 1));
    }

    static int countNaive(int limit) { int c = 0; for (int i = 2; i < limit; i++) if (isPrimeNaive(i)) c++; return c; }
    static int countSqrt(int limit)  { int c = 0; for (int i = 2; i < limit; i++) if (isPrimeSqrt(i)) c++; return c; }
    static int count6k(int limit)    { int c = 0; for (int i = 2; i < limit; i++) if (isPrime6k(i)) c++; return c; }
    static int countBig(int limit)   { int c = 0; for (int i = 2; i < limit; i++) if (isPrimeBig(i)) c++; return c; }
    static int countSieve(int limit) {
        boolean[] comp = sieve(limit - 1);
        int c = 0; for (int i = 2; i < limit; i++) if (!comp[i]) c++; return c;
    }
}