
import java.io.*;
import java.text.DecimalFormat;

/**
 * sieve of Eratosthenes using a primitive bit array using bit-shift and bit-and
 * using multiple passes to reduce memory footprint; writing primes to disk files.
 * <p/>
 * ported from http://www.troubleshooters.com/codecorn/primenumbers/primenumbers.htm
 * <p/>
 * Created by Xan Gregg.
 * Date: Nov 13, 2004
 */
public class FindPrimes8 {

    public static void main(String[] args) {
        try {
            // find primes less that 100 million in one array
            long start = System.currentTimeMillis();
            long count = FindPrimes7.findPrimes(1000000000, new PrintStream(new NullOutputStream()));
            long end = System.currentTimeMillis();
            long elapsed = end - start;
            System.out.println("Primes: " + count + "; seconds: " + elapsed / 1000.0);

            // find and record primes less than 1 million
            start = System.currentTimeMillis();
            File file0 = new File("0.pri");
            PrintStream out = new PrintStream(new BufferedOutputStream(new FileOutputStream(file0)));
            count = FindPrimes7.findPrimes(10000000, out);
            out.close();
            end = System.currentTimeMillis();
            elapsed = end - start;
            System.out.println("Primes: " + count + "; seconds: " + elapsed / 1000.0);

            // find and record between 1 million and 100 million a page at a time
            start = System.currentTimeMillis();
            count = findPrimes(10000000, 1, 99);
            end = System.currentTimeMillis();
            elapsed = end - start;
            System.out.println("Primes: " + count + "; seconds: " + elapsed / 1000.0);


        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    static class BITARRAY {
        int[] bits;
        long pageno;
        long bitsInArray;
        long offset;
    }

    private static BITARRAY createBitArray(long bits, long pageno) {
        BITARRAY ba = new BITARRAY();
        ba.pageno = pageno;
        ba.bitsInArray = bits;
        ba.offset = ba.pageno * ba.bitsInArray;
        ba.bits = new int[(int) (bits >> 5) + 1];
        return ba;
    }

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

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

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

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

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

    private static long[] makePrimeArray(String fname) throws IOException {
        FileReader fr = new FileReader(fname);
        BufferedReader fin = new BufferedReader(fr);

        /* FIND NUMBER OF LINES */
        long lineCount = 0;
        while (fin.readLine() != null)
            lineCount++;

        /* ALLOCATE ARRAY */
        long[] factors = new long[(int) lineCount];

        /* READ THE PRIMES INTO factors */
        fin.close();
        fr = new FileReader(fname);
        fin = new BufferedReader(fr);
        lineCount = 0;
        for (String line = fin.readLine(); line != null; line = fin.readLine()) {
            factors[(int) lineCount] = Long.parseLong(line);
            lineCount++;
        }
        fin.close();
        return factors;
    }

    private static long findPrimesInOnePage(long topCandidate, long pageno, long[] factors, BITARRAY ba) throws IOException {
        long count = 0;
        long ss;

        /* SET ba ELEMENTS */
        ba.pageno = pageno;
        ba.offset = ba.pageno * ba.bitsInArray;

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

        /* MARK ALL THE NON-PRIMES */
        long factorSS = 0;
        long thisFactor = factors[(int) factorSS];
        while (thisFactor != 0 && thisFactor * thisFactor <= topCandidate + ba.offset) {
            /* MARK THE MULTIPLES OF THIS FACTOR */
            long mark = thisFactor + thisFactor;
            if (mark < ba.offset) {
                mark = (ba.offset / thisFactor) * thisFactor;
                if (mark < ba.offset)
                    mark += thisFactor;
            }
            mark -= ba.offset;
            while (mark <= topCandidate) {
                clearBit(ba, mark);
                mark += thisFactor;
            }

            /* SET thisFactor TO NEXT PRIME */
            factorSS++;
            thisFactor = factors[(int) factorSS];
            //assert(thisFactor <= topCandidate + ba - > offset);
        }

        /* PRINT ALL THE PRIMES */
        DecimalFormat nf = new DecimalFormat();
        nf.setGroupingUsed(false);
        nf.setMinimumIntegerDigits(8);
        FileWriter fw = new FileWriter("pri" + nf.format(pageno) + ".pri");
        BufferedWriter fout = new BufferedWriter(fw);
        //FileOutputStream fw = new FileOutputStream("pri" + nf.format(pageno) + ".pri");
        //PrintStream fout = new PrintStream(new BufferedOutputStream(fw));

        for (ss = 0; ss <= topCandidate; ss++) {
            if (getBit(ba, ss)) {
                fout.write(Long.toString(ss + ba.offset) + "\n");
                //fout.println(ss + ba.offset);
                count ++;
            }
        }
        fout.close();
        return count;
    }

    public static long findPrimes(long numbersPerPage, long startPageno, long pagesToProcess) throws IOException {
        long pageCount;

        /* PUT FACTORS IN AN ARRAY */
        long[] factors = makePrimeArray("0.pri");
        long count = factors.length;


        /* CREATE BITARRAY */
        BITARRAY ba = createBitArray(numbersPerPage, startPageno);

        /* PROCESS EVERY PAGE */
        for (pageCount = 0; pageCount < pagesToProcess; pageCount++) {
            count += findPrimesInOnePage(numbersPerPage, pageCount + startPageno,
                            factors, ba);
        }
        return count;
    }

}
