//	Primes.java - Answer some questions about prime numbers
//
//	o How many prime numbers are there less than MAXINT?
//	o What's the largest prime number less than MAXINT?
//	o Is that prime one half of a prime pair?
//	o Calculate the number of primes/ms that are discovered.
//
//	Primes [VERBOSE | DIVISION | SAVED | SIEVE] -- which kind of calculation to use
//
//	Bary W Pollack  -  Feb. 18, 2006  -  14:00

import java.text.DecimalFormat;
import java.util.Calendar;
import java.util.Vector;

enum Kind { VERBOSE, DIVISION, SAVED, SIEVE };

public class Primes {

	Primes() {
		System.out.println(LS + "Prime Numbers Less Than MAXINT (" + prettyNum(MAX)
							  + ")  Kind=" + kind);
		System.out.println("===========================================" + LS);

		// Create a sieve
		sieve = new Sieve();
		nStart = sieve.getNstart();
		nOffsets = sieve.getNoffsets();
		if (DBG)
			System.out.println("nStart = " + nStart + ",  " 
								+ nOffsets.length + " offsets" + LS);

		// Find prime numbers
		int nCount = 0;
		Calendar rightNow = Calendar.getInstance();
		long lNowInMillis = rightNow.getTimeInMillis();
		switch (kind) {

		  case VERBOSE:
			for (int i = 2; i <= MAX; i++) {
				String sNumber = prettyNum(i);
				if (isPrime1(i)) {
					++nCount;  nLastPrime2 = nLastPrime1;  nLastPrime1 = i;
					System.out.println(pad(sNumber, MAX_WIDTH) + " prime");
				} else {
					System.out.println(pad(sNumber, MAX_WIDTH));
				}
			}
			System.out.println();
			break;

		  case DIVISION:
			nCount = 1;
			for (int i = 3; i <= MAX; i += 2) {
				if (isPrime2(i)) {
					++nCount;  nLastPrime2 = nLastPrime1;  nLastPrime1 = i;
				}
			}
			break;

		  case SAVED:
			nCount = 7;				// 2 3 5 7 11 13 17
			numPrimes = 0;
			/// nPrimes = new int[1000];
			for (int i = nStart, nIndex = 0; i <= MAX; ++nIndex) {
				if (isPrime4(i)) {
					++nCount;  nLastPrime2 = nLastPrime1;  nLastPrime1 = i;
				}
				i += nOffsets[nIndex % nOffsets.length];
			}
			break;

		  case SIEVE:
			nCount = 7;				// 2 3 5 7 11 13 17
			for (int i = nStart, nIndex = 0; i <= MAX; ++nIndex) {
				if (isPrime3(i)) {
					++nCount;  nLastPrime2 = nLastPrime1;  nLastPrime1 = i;
				}
				i += nOffsets[nIndex % nOffsets.length];
			}
			break;

		  default:
		  	System.out.println("ERROR:  Bad kind -- not VERBOSE, DIVISION, SAVED, SIEVE");
		}

		rightNow = Calendar.getInstance();
		long lElapsedMillis = rightNow.getTimeInMillis() - lNowInMillis;
		System.out.println("The largest two primes less than MAXINT are: " 
							+ prettyNum(nLastPrime2) + " and " 
							+ prettyNum(nLastPrime1)
							+ ((nLastPrime2 + 2 == nLastPrime1) ? ", twins" : ", not twins"));
		System.out.println("There are " + prettyNum(nCount) 
							+ " primes less than " + prettyNum(MAX));
		if (lElapsedMillis <= 0)
			lElapsedMillis = 1;
		System.out.println("Computed in " + lElapsedMillis + " ms; "
							+ Math.round(((double) nCount)/lElapsedMillis) + " primes/ms");
	}

	String prettyNum(int nNumber) {
		return myFormatter.format(nNumber);
	}

	public static String pad(String s, final int MAX_WIDTH) {
		final int nWidth = MAX_WIDTH - s.length();
		for (int i = 0; i < nWidth; i++)
			s = " " + s;
		return s;
	}

	// handles all numbers >= 2
	boolean isPrime1(int nNumber) {
		boolean bIsPrime = true;

		if ((nNumber & 1) == 0) {
			if (nNumber != 2)
				bIsPrime = false;
		} else {
			int nLimit = (int) Math.sqrt(nNumber);
			for (int iDivisor = 3; iDivisor <= nLimit; iDivisor += 2)
				if (nNumber % iDivisor == 0) {
					bIsPrime = false;
					break;
				}
		}
		return bIsPrime;
	}

	// handles all odd numbers >= 3
	boolean isPrime2(int nNumber) {
		boolean bIsPrime = true;
		int nLimit = (int) Math.sqrt(nNumber);

		for (int iDivisor = 3; iDivisor <= nLimit; iDivisor += 2)
			if (nNumber % iDivisor == 0) {
				bIsPrime = false;
				break;
			}
		return bIsPrime;
	}

	// handles all prime candidates, and odd divisors >= nStart
	boolean isPrime3(int nNumber) {
		boolean bIsPrime = true;
		int nLimit = (int) Math.sqrt(nNumber);

		for (int iDivisor = nStart; iDivisor <= nLimit; iDivisor += 2)
			if (nNumber % iDivisor == 0) {
				bIsPrime = false;
				break;
			}
		return bIsPrime;
	}

	// handles all prime divisors in the nPrimes array; then uses isPrime3
	boolean isPrime4(int nNumber) {
		boolean bIsPrime = true;

		for (int i = 0; i < numPrimes; i++) {
			if (nNumber % nPrimes[i] == 0) {
				bIsPrime = false;
				break;
			}
		}
		if (bIsPrime) {
			if (numPrimes > 0)
				nStart = nPrimes[numPrimes-1] + 2;
			bIsPrime = isPrime3(nNumber);
			if (bIsPrime && (numPrimes < nPrimes.length - 1))
				nPrimes[numPrimes++] = nNumber;
		}
		return bIsPrime;
	}

	public static void main(String[] args) {
		if (args.length > 0) {
			if (args.length < 2) {
				System.out.println("Usage:  java Primes #MB kind");
				System.exit(0);
			}
			MAX = 1024 * Integer.parseInt(args[0]);
			if (args[1].compareToIgnoreCase("VERBOSE") == 0)
				kind = Kind.VERBOSE;
			else if (args[1].compareToIgnoreCase("DIVISION") == 0)
				kind = Kind.DIVISION;
			else if (args[1].compareToIgnoreCase("SAVED") == 0)
				kind = Kind.SAVED;
			else if (args[1].compareToIgnoreCase("SIEVE") == 0)
				kind = Kind.SIEVE;
		}
		new Primes();
		System.out.println();
	}

	public static int MAX = 32*1024*1024;		// The maximum value

	public static final String LS = System.getProperty("line.separator");
	public static final int MAXINT = Integer.MAX_VALUE;
	public static final int MAX_WIDTH = 12;
	private static final String sPattern = "###,###";
	private static final DecimalFormat myFormatter = new DecimalFormat(sPattern);
	private int nLastPrime1 = -1;
	private int nLastPrime2 = -1;
	private int numPrimes = 0;
	private int[] nPrimes = new int[700];		// 700 for 32 M

	private Sieve sieve;
	private int nStart;
	private int[] nOffsets;

	private static Kind kind = Kind.SAVED;
	private static final boolean DBG = true;

}

//	Sieve creates a residue sieve, eliminating multiples of small primes

class Sieve {
	Sieve() {
		final int LOW_PRIMES = 2*3*5*7*11*13*17;			//FOO
		if (DBG)
			System.out.println("Create a Sieve" + Primes.LS);
		sieve = new byte[2 * LOW_PRIMES];
		for (int i = 17; i < sieve.length; i += 17)
			sieve[i] = 17;
		for (int i = 13; i < sieve.length; i += 13)
			sieve[i] = 13;
		for (int i = 11; i < sieve.length; i += 11)
			sieve[i] = 11;
		for (int i = 7;  i < sieve.length; i += 7)
			sieve[i] = 7;
		for (int i = 5;  i < sieve.length; i += 5)
			sieve[i] = 5;
		for (int i = 3;  i < sieve.length; i += 3)
			sieve[i] = 3;
		for (int i = 2;  i < sieve.length; i += 2)
			sieve[i] = 2;
		/// displaySieve();
		nOffsets = calculateOffsets(LOW_PRIMES);
		if (DBG) {
			displayOffsets();
			displayCandidates();
		}
		sieve = null;
	}

	int getNstart() { return nStart; }

	int[] getNoffsets() { return nOffsets; }

	private void displaySieve() {
		System.out.print("        ");
		for (int i = 0; i < 10; i++)
			System.out.print(i + " ");
		System.out.println();
		for (int i = 0; i < sieve.length; i += 10) {
			System.out.print(Primes.pad("" + i, 5) + ":  ");
			for (int j = i; j < i + 10; j++)
				System.out.print(sieve[j] + " ");
			System.out.println();
		}
	}

	private int[] calculateOffsets(final int nSize) {
		int i, offset, nCand;
		Vector<Integer> vOffsets = new Vector<Integer>();
		for (i = 3; sieve[i] != 0; i++)
			;
		nStart = nCand = i;
		/// System.out.print(i + ": ");
		while (i < sieve.length) {
			offset = 1;
			while (sieve[++i] != 0)
				++offset;
			/// System.out.print(offset + " ");
			vOffsets.add(offset);
			nCand += offset;
			if (nCand >= nStart+nSize)
				break;
		}
		/// System.out.println();
		int[] nOffsets = new int[vOffsets.size()];
		for (i = 0; i < nOffsets.length; i++)
			nOffsets[i] = vOffsets.elementAt(i);
		return nOffsets;
	}

	private void displayOffsets() {
		System.out.print("Offsets:    ");
		for (int i = 0; i < nOffsets.length; i++) {
			if ((i > 0) && (i % 10) == 0)
				System.out.print("  ");
			if ((i > 0) && (i % 20) == 0)
				System.out.print(Primes.LS + "            ");
			System.out.print(" " + nOffsets[i]);
		}
		System.out.println(" (" + nOffsets.length + ")");
	}

	private void displayCandidates() {
		int nCand = nStart;
		int nCount = 0;
		System.out.print("Candidates:  " + nCand);
		for (int i = 0; i <= 2*nOffsets.length; i++) {
			if ((i > 0) && (i % 10 == 0))
				System.out.print("   ");
			if ((i > 0) && (i % 20 == 0))
				System.out.print(Primes.LS + "            ");
			if ((i % nOffsets.length) == 0)
				System.out.print(" |");
			nCand += nOffsets[i % nOffsets.length];
			System.out.print(" " + nCand);
			++nCount;
		}
		System.out.println(" (" + nCount + ")");
	}

	private byte[] sieve;
	private int nStart;
	private int[] nOffsets;
	private static final boolean DBG = false;
}