package coreservlets;

import java.math.BigInteger;

/** Kilka narzędzi pomocniczych do generowania dużej
 *  losowej liczby BigInteger i wyznaczenia większej od niej,
 *  najbliższej jej liczby pierwszej.
 *  <P>
 *  Taken from Core Servlets and JavaServer Pages Volume II
 *  from Prentice Hall and Sun Microsystems Press,
 *  http://volume2.coreservlets.com/.
 *  (C) 2007 Marty Hall, Larry Brown, and Yaakov Chaikin;
 *  may be freely used or adapted.
 */

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");

  // Prawdpodobieństwo wyznaczenia błędnej liczby pierwszej
  // jest mniejsze niż 1/2^ERR_VAL.
  // Z założenia BigInteger używa testu Millera-Rabina
  // lub jego odpowiednika, dzięki czemu NIE występują
  // zakłócenia liczbami Carmichaela.
  // Więcej szczegółowych informacji znajduje się w punkcie 33.8 
  // książki Cormena i innych pt. Introduction to Algorithms.
  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]);
  }

  /** Utworzenie dużej, losowej liczby całkowitej, w której
   *  każda cyfra jest wybierana losowo (z wyjątkiem pierwszej,
   *  która nie może być zerem).
   */

  public static BigInteger random(int numDigits) {
    StringBuffer s = new StringBuffer("");
    for(int i=0; i<numDigits; i++) {
      if (i == 0) {
        // Pierwszą cyfrą nie może być zero.
        s.append(randomDigit(false));
      } else {
        s.append(randomDigit(true));
      }
    }
    return(new BigInteger(s.toString()));
  }

  /** Program testowy działający w wierszu poleceń.
   *  Wystarczy wpisać liczbę cyfr, a program wygeneruje 
   *  losową liczbę o wskazanej długości i zwróci pierwszych 
   *  pięćdziesiąt liczb pierwszych, które są od niej większe.
   */

  public static void main(String[] args) {
    int numDigits;
    try {
      numDigits = Integer.parseInt(args[0]);
    } catch (Exception e) { // Brak argumentów lub argumenty nieprawidłowe.
      numDigits = 150;
    }
    BigInteger start = random(numDigits);
    for(int i=0; i<50; i++) {
      start = nextPrime(start);
      System.out.println("Liczba pierwsza " + i + " = " + start);
    }
  }
}
