
import java.io.PrintStream;

/**
 * sieve of Eratosthenes
 * <p/>
 * ported from http://www.troubleshooters.com/codecorn/primenumbers/primenumbers.htm
 * <p/>
 * Created by Xan Gregg.
 * Date: Nov 13, 2004
 */
public class FindPrimes5 {

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        //long count = findPrimes(10000, System.out);
        long count = findPrimes(10000000, new PrintStream(new NullOutputStream()));
        long end = System.currentTimeMillis();
        long elapsed = end - start;
        System.out.println("Primes: " + count + "; seconds: " + elapsed / 1000.0);
    }

    public static long findPrimes(long topCandidate, PrintStream out) {
        long count = 0;
        boolean array[] = new boolean[(int) topCandidate + 1];

        /* SET ALL BUT 0 AND 1 TO PRIME STATUS */
        int ss;
        for (ss = 0; ss <= topCandidate; ss++)
            array[ss] = true;
        array[0] = false;
        array[1] = false;

        /* MARK ALL THE NON-PRIMES */
        long thisFactor = 2;
        long lastSquare = 0;
        long thisSquare;
        while (thisFactor * thisFactor <= topCandidate) {
            /* MARK THE MULTIPLES OF THIS FACTOR */
            long mark = thisFactor + thisFactor;
            while (mark <= topCandidate) {
                array[(int) mark] = false;
                mark += thisFactor;
            }

            /* PRINT THE PROVEN PRIMES SO FAR */
            thisSquare = thisFactor * thisFactor;
            for (; lastSquare < thisSquare; lastSquare++) {
                if (array[(int) lastSquare]) {
                    out.println(lastSquare);
                    count ++;
                }
            }

            /* SET thisFactor TO NEXT PRIME */
            thisFactor++;
            while (array[(int) thisFactor] == false)
                thisFactor++;
        }

        /* PRINT THE REMAINING PRIMES */
        for (; lastSquare <= topCandidate; lastSquare++) {
            if (array[(int) lastSquare]) {
                out.println(lastSquare);
                count ++;
            }
        }
        return count;
    }

}
