
import java.io.PrintStream;

/**
 * brute force search for factors using only previously found primes as factors
 * skip even numbers
 *
 * ported from http://www.troubleshooters.com/codecorn/primenumbers/primenumbers.htm
 *
 * Created by Xan Gregg.
 * Date: Nov 13, 2004
 */
public class FindPrimes3 {

    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);
    }

    static class primerec {
        public long prime;
        public primerec next;
    }


    public static long findPrimes(long topCandidate, PrintStream out) {
        out.println(2);
        long count = 1;
        primerec firstPrime = new primerec();
        primerec latestPrime = firstPrime;
        firstPrime.prime = 3;
        long candidate = 3;
        while (candidate <= topCandidate) {
            primerec thisPrime = firstPrime;
            boolean prime = true;
            while (thisPrime.prime * thisPrime.prime <= candidate) {
                if (candidate % thisPrime.prime == 0) {
                    prime = false;
                    break;
                }
                thisPrime = thisPrime.next;
            }
            if (prime) {
                out.println(candidate);
                count ++;
                latestPrime.next = new primerec();
                latestPrime = latestPrime.next;
                latestPrime.prime = candidate;
            }
            candidate += 2;
        }
        return count;
    }

}
