
import java.io.PrintStream;

/**
 * sieve of Eratosthenes using a primitive bit array using bit-shift and bit-and
 * <p/>
 * ported from http://www.troubleshooters.com/codecorn/primenumbers/primenumbers.htm
 * <p/>
 * Created by Xan Gregg.
 * Date: Nov 13, 2004
 */
public class FindPrimes7 {

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

    private static int[] createBitArray(long bits) {
        return new int[(int) (bits >> 5) + 1];
    }

    private static void setBit(int ba[], long bitSS) {
        ba[(int) (bitSS >> 5)] |= 1 << (bitSS & 31);
    }

    private static void clearBit(int ba[], long bitSS) {
        ba[(int) (bitSS >> 5)] &= ~(1 << (bitSS & 31));
    }

    private static boolean getBit(int ba[], long bitSS) {
        int cell = ba[(int) (bitSS >> 5)];
        return (cell & (1 << (bitSS & 31))) != 0;
    }

    private static void clearAll(int ba[]) {
        for (int ss = 0; ss < ba.length; ss++)
            ba[ss] = 0;
    }

    private static void setAll(int ba[]) {
        for (int ss = 0; ss < ba.length; ss++)
            ba[ss] = -1;
    }

    public static long findPrimes(long topCandidate, PrintStream out) {
        long count = 0;
        int[] ba = createBitArray(topCandidate);

        /* SET ALL BUT 0 AND 1 TO PRIME STATUS */
        setAll(ba);
        clearBit(ba, 0);
        clearBit(ba, 1);

        /* 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) {
                clearBit(ba, mark);
                mark += thisFactor;
            }

            /* PRINT THE PROVEN PRIMES SO FAR */
            thisSquare = thisFactor * thisFactor;
            for (; lastSquare < thisSquare; lastSquare++) {
                if (getBit(ba, lastSquare)) {
                    out.println(lastSquare);
                    count ++;
                }
            }

            /* SET thisFactor TO NEXT PRIME */
            thisFactor++;
            while (!getBit(ba, thisFactor))
                thisFactor++;
        }

        /* PRINT THE REMAINING PRIMES */
        for (; lastSquare <= topCandidate; lastSquare++) {
            if (getBit(ba, lastSquare)) {
                out.println(lastSquare);
                count ++;
            }
        }
        return count;
    }

}
