import static java.lang.Math.*;

public class WheelPrimes implements Runnable {
    static final int[] FIRST_PRIMES = {2,3,5,7,11,13,17,19};

    public static void main (String...args) {
        final long maxValue = args.length < 1 ? 1000000 : (long)Double.parseDouble(args[0]);

        if (maxValue < 0 || maxValue == Long.MAX_VALUE) {
            System.out.println("N must be less than " + Long.MAX_VALUE);
            System.exit(-1);
        }

        // number of primes in wheel
        final int  m = args.length < 2 ? 5 : Integer.parseInt(args[1]);

        if (m < 2 || m > 7) {
            System.out.println("m must be between 2 and 7");
            System.exit(-1);
        }

        (new WheelPrimes(maxValue, m)).run();
    }

    final long  maxValue;
    final long  maxSqrt;
    final int   wheel;
    final int   composites;
    final int   m;
    final int[] blockIndices;
    final int[] bitMasks;
    final int[] offsets;

    WheelPrimes (long maxValue, int m) {
        this.maxValue   = maxValue;
        this.m          = m;

        maxSqrt = (long)ceil(sqrt(maxValue));

        // wheel consists of product of first m primes.
        {
            int wheel = 1;

            for (int i = 0; i < m; ++i)
                wheel *= FIRST_PRIMES[i];

            this.wheel = wheel;
        }


        // mark known composites mod wheel
        boolean[] mask = new boolean[wheel];

        for (int i = 0; i < m; ++i) {
            final int prime = FIRST_PRIMES[i];

            for (int j = prime; j < wheel; j += prime) {
                mask[j] = true;
            }
        }

        mask[0] = true; // wheel * x is composite

        {
            int composites = 0;

            for (int i = 0; i < wheel; ++i)
                if (!mask[i])
                    ++composites;

            this.composites = composites;
        }

        blockIndices = new int[wheel];
        bitMasks     = new int[wheel];
        offsets      = new int[composites];

        // for each int in the wheel, record its mask
        for (int i = 0, bit = 0; i < wheel; ++i) {
            if (!mask[i]) {
                blockIndices[i] = bit / 32;
                bitMasks[i]   = 1 << (bit & 31);
                offsets[bit]  = i;
                ++bit;
            }
        }
    }

    public void run () {
        // if max is very small, just use the hard-coded primes
        if (maxValue <= FIRST_PRIMES[FIRST_PRIMES.length - 1]) {
            for (long prime : FIRST_PRIMES) {
                if (prime > maxValue) break;
                printPrime(prime);
            }
            return;
        }

        // at most, we need to use m + (composites/wheel) * sqrt(maxValue) primes for marking
        final int    numberOfMarkingPrimes  = (int) ((composites * maxSqrt + wheel - 1)/wheel);
        final long[] markingPrimes          = new long[numberOfMarkingPrimes];
        final long[] markingPrimeCounters   = new long[numberOfMarkingPrimes];
        int          markingPrimeCount      = 0;

        // each block represents (wheel) numbers using (composites) bits
        final int blockSize = (composites + 31) / 32; // number of ints in block

        System.out.println("m:          " + m + " (number of primes in the wheel)");
        System.out.println("wheel:      " + wheel);
        System.out.println("composites: " + composites + " (" + ((100L*composites)/wheel) + "% of wheel)");
        System.out.println("max:        " + maxValue);
        System.out.println("max/wheel:  " + (maxValue/wheel) + " banks");
        System.out.println("block size: " + (blockSize * 4) + " bytes");
        System.out.println("marking prime array size: " + (numberOfMarkingPrimes) + " entries, " + ((numberOfMarkingPrimes*8*2)/1024) + " kiB");
        System.out.println();


        final long minMarkingPrime = FIRST_PRIMES[m];

        // start printing primes
        // print the ones used to seed the wheel
        for (int i = 0; i < m; ++i)
            printPrime(FIRST_PRIMES[i]);

        // using an array representing a block of numbers, start printing primes
        final int[] block = new int[blockSize];

        // on the first run ignore 0 * wheel + 1
        block[0] = 1;

        long blockBase = 0;

        for (; blockBase < maxSqrt; blockBase += wheel) {
            // mark block with marking primes
            for (int i = 0; i < markingPrimeCount; ++i) {
                final long  markingPrime        = markingPrimes[i];
                long        markingPrimeCounter = markingPrimeCounters[i];

                for (; markingPrimeCounter < wheel; markingPrimeCounter += markingPrime)
                    block[blockIndices[(int)markingPrimeCounter]] |= bitMasks[(int)markingPrimeCounter];

                markingPrimeCounters[i] = markingPrimeCounter - wheel;
            }

            // scan block for un-marked values
            for (int i = 0; i < blockSize; ++i) {
                final int datum = block[i];

                for (int bit = 0; bit < 32; ++bit) {
                    if ((datum & (1 << bit)) == 0) {
                        long  index = i * 32 + bit;

                        if (index < composites) {
                            final long prime = blockBase + offsets[i * 32 + bit];

                            if (prime >= minMarkingPrime && prime <= maxSqrt) {
                                // if the prime is less than the sqrt of the max value,
                                // it's a marking prime so add it to the list
                                if (markingPrimeCount < numberOfMarkingPrimes) {
                                    markingPrimes[markingPrimeCount] = prime;

                                    // mark the rest of the block with this prime
                                    long        markingPrimeCounter = prime * prime - blockBase;

                                    for (; markingPrimeCounter < wheel; markingPrimeCounter += prime)
                                        block[blockIndices[(int)markingPrimeCounter]] |= bitMasks[(int)markingPrimeCounter];

                                    markingPrimeCounters[markingPrimeCount] = markingPrimeCounter - wheel;

                                    ++markingPrimeCount;
                                }
                            }

                            if (prime > maxValue) break;

                            printPrime(prime);
                        }
                    }
                }
            }

            // reset block for next iteration
            for (int i = 0; i < blockSize; ++i) {
                block[i] = 0;
            }
        }

        System.out.println("last of " + markingPrimeCount + " marking primes after " + (System.currentTimeMillis() - startTime) + "ms");

        if (markingPrimeCount > 0) {
            for (int lo = 0, hi = markingPrimeCount-1; ; ) {
                final int mid = (lo + hi) / 2;

                if (markingPrimes[mid] < wheel)
                    lo = mid;
                else
                    hi = mid;

                if (hi <= lo + 1) {
                    System.out.println(lo + " primes below wheel (" + ((lo * 100) / markingPrimeCount) + "% of marking primes)");
                    break;
                }
            }
        }

        // this bit should parallelise on the CPU-
        //   for threads k in range(0,K),  each processing L blocks
        //     take a copy of markingPrimeCounters and a new block
        //     for each marking prime
        //       increment markingPrimeCounter by k * L * wheel mod markingPrime
        //     blockBase ranges from blockBase + k * L * wheel to ((k + 1) * L * wheel - 1)
        // need to synchronize results generation
        // can't think of a good way to parallelise on GPU -
        //  although using a bitmap as the seive is possible, as most of the marking primes
        //  contribute less than one mark per block, it's unlikely to be efficient
        mainScan:
        for (; blockBase < maxValue; blockBase += wheel) {
            // mark block with marking primes
            for (int i = 0; i < markingPrimeCount; ++i) {
                final long  markingPrime        = markingPrimes[i];
                long        markingPrimeCounter = markingPrimeCounters[i];

                for (; markingPrimeCounter < wheel; markingPrimeCounter += markingPrime)
                    block[blockIndices[(int)markingPrimeCounter]] |= bitMasks[(int)markingPrimeCounter];

                markingPrimeCounters[i] = markingPrimeCounter - wheel;
            }

            // scan block for un-marked values
            for (int i = 0; i < blockSize; ++i) {
                final int datum = block[i];

                for (int bit = 0; bit < 32; ++bit) {
                    if ((datum & (1 << bit)) == 0) {
                        long  index = i * 32 + bit;

                        if (index < composites) {
                            final long prime = blockBase + offsets[i * 32 + bit];

                            if (prime > maxValue)
                                break mainScan;

                            printPrime(prime);
                        }
                    }
                }
            }

            // reset block for next iteration
            for (int i = 0; i < blockSize; ++i) {
                block[i] = 0;
            }
        }

        System.out.println("found " + primeCount + " primes below " + maxValue + ".");
    }

    static long startTime = System.currentTimeMillis();
    static long primeCount;
    static long primeBand = 10000;

    static void printPrime (long prime) {
        ++primeCount;

        //~ System.out.println("prime " + prime);

        if (prime > primeBand) {
            System.out.println((primeCount - 1) + "\tprimes below " + primeBand + "\tafter " + (System.currentTimeMillis() - startTime) + "ms");
            primeBand *= 10;
        }
    }
}