package coreservlets;
import java.math.BigInteger;

/** A few utilities to generate a large random BigInteger,
* and find the next prime number above a given BigInteger.
*/

public class Primes {
	
	// Note that BigInteger.ZERO was new in JDK 1.2, and 1.1
	// code is being used to support the most servlet engines.

	private static final BigInteger ZERO = new BigInteger("0");
	private static final BigInteger ONE = new BigInteger("1");
	private static final BigInteger TWO = new BigInteger("2");
	
	// Likelihood of false prime is less than 1/2^ERR_VAL
	// Assumedly BigInteger uses the Miller-Rabin test or
	// equivalent, and thus is NOT fooled by Carmichael numbers.
	// See section 33.8 of Cormen et al’s Introduction to
	// Algorithms for details.

	private static final int ERR_VAL = 100;

	public static BigInteger nextPrime(BigInteger start) {
		if (isEven(start))
			start = start.add(ONE);
		else
			start = start.add(TWO);
		if (start.isProbablePrime(ERR_VAL))
			return(start);
		else
			return(nextPrime(start));
	}

	private static boolean isEven(BigInteger n) {
		return(n.mod(TWO).equals(ZERO));
	}

	private static StringBuffer[] digits =
		{ new StringBuffer("0"), new StringBuffer("1"),
		new StringBuffer("2"), new StringBuffer("3"),
		new StringBuffer("4"), new StringBuffer("5"),
		new StringBuffer("6"), new StringBuffer("7"),
		new StringBuffer("8"), new StringBuffer("9") };
	
	private static StringBuffer randomDigit() {
		int index = (int)Math.floor(Math.random() * 10);
		return(digits[index]);
	}

	public static BigInteger random(int numDigits) {
		StringBuffer s = new StringBuffer("");
		for(int i=0; i<numDigits; i++) {
			s.append(randomDigit());
		}
		return(new BigInteger(s.toString()));
	}

	/** Simple command-line program to test. Enter number
	* of digits, and it picks a random number of that
	* length and then prints the first 50 prime numbers
	* above that.
	*/

	public static void main(String[] args) {
		int numDigits;
		if (args.length > 0)
			numDigits = Integer.parseInt(args[0]);
		else
			numDigits = 150;
		BigInteger start = random(numDigits);
		for(int i=0; i<50; i++) {
			start = nextPrime(start);
		System.out.println("Prime " + i + " = " + start);
		}
	}
}