Primes.java

import java.util.ArrayList;
import java.util.BitSet;

/**
 * Created by Tobias on 24/04/2015.
 */
public class Primes {
    public static interface Solution {
        String getAlgorithm();

        int numPrimesBelow(int n);
    }

    // 0.4s
    public static class SieveSolution implements Solution {
        @Override
        public String getAlgorithm() {
            return "Sieve";
        }

        @Override
        public int numPrimesBelow(int n) {
            BitSet sieve = new BitSet(n + 1);

            // assume everything is a prime
            sieve.set(0, n);

            // get rid of numbers before first actual prime (2)
            sieve.clear(0);
            sieve.clear(1);

            // get rid of all multiples of primes
            int primes = 0;
            for (int i = 1; i < n; i++) {
                if (sieve.get(i)) {
                    primes++;
                    int prime = i;

                    int val = prime + prime;
                    while (val < n) {
                        sieve.clear(val);

                        val += prime;
                    }
                }
            }
            return primes++;
        }
    }

    // ~3.0 seconds
    public static class SqrtHistorySolution implements Solution {
        @Override
        public String getAlgorithm() {
            return "Sqrt History";
        }

        @Override
        public int numPrimesBelow(int n) {
            ArrayList<Integer> primes = new ArrayList<Integer>();

            if (n < 2) {
                return 0;
            }

            primes.add(2);
            for (int primeCandidate = 3; primeCandidate < n; primeCandidate++) {
                boolean isPrime = true;

                double sqrt = Math.ceil(Math.sqrt(primeCandidate));
                for (Integer prime : primes) {
                    if (prime > sqrt) {
                        break;
                    }
                    if (primeCandidate % prime == 0) {
                        isPrime = false;
                        break;
                    }
                }
                if (isPrime) {
                    primes.add(primeCandidate);
                }
            }

            return primes.size();
        }
    }

    // ~30.7 seconds
    public static class NaiveSqrtSolution implements Solution {
        @Override
        public String getAlgorithm() {
            return "Naive Sqrt Solution";
        }

        private boolean isPrime(int n) {
            if (n == 2) {
                return true;
            }
            for (int i = 2; i <= Math.ceil(Math.sqrt(n)); i++) {
                if (n % i == 0) {
                    return false;
                }
            }
            return true;
        }

        @Override
        public int numPrimesBelow(int n) {
            int primes = 0;
            for (int i = 2; i < n; i++) {
                if (isPrime(i)) {
                    primes++;
                }
            }
            return primes;
        }
    }

    public static void main(String[] args) {
        Solution[] solutions = {
                new SieveSolution(),
                new SqrtHistorySolution(),
                new NaiveSqrtSolution()
        };

        for (Solution s : solutions) {
            long startTime = System.nanoTime();
            int numPrimes = s.numPrimesBelow(10000000);
            long endTime = System.nanoTime();

            System.out.printf("Found %d primes in %d ms using %s\n", numPrimes, (endTime - startTime) / 1000000, s.getAlgorithm());
        }
    }
}