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. *  <p> *  From <a href="http://courses.coreservlets.com/Course-Materials/">the *  coreservlets.com tutorials on servlets, JSP, Struts, JSF, Ajax, GWT,  *  Spring, Hibernate/JPA, and Java programming</a>. */public class Primes {  private static final BigInteger ZERO = BigInteger.ZERO;  private static final BigInteger ONE = BigInteger.ONE;  private static final BigInteger TWO = new BigInteger("2");    // Likelihood of false prime is less than 1/2^ERR_VAL.  // Presumably 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(boolean isZeroOK) {    int index;    if (isZeroOK) {      index = (int)Math.floor(Math.random() * 10);    } else {      index = 1 + (int)Math.floor(Math.random() * 9);    }    return(digits[index]);  }  /** Create a random big integer where every digit is   *  selected randomly (except that the first digit   *  cannot be a zero).   */    public static BigInteger random(int numDigits) {    StringBuffer s = new StringBuffer("");    for(int i=0; i<numDigits; i++) {      if (i == 0) {        // First digit must be non-zero.        s.append(randomDigit(false));       } else {        s.append(randomDigit(true));      }    }    return(new BigInteger(s.toString()));  }  /** Simple command-line program to test. Enter number   *  of digits, and the program 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;    try {      numDigits = Integer.parseInt(args[0]);    } catch (Exception e) { // No args or illegal arg.      numDigits = 150;    }    BigInteger start = random(numDigits);    for(int i=0; i<50; i++) {      start = nextPrime(start);      System.out.println("Prime " + i + " = " + start);    }  }    private Primes() {} // Uninstantiatable class}