/**
Algorithms from  Olivier Langlois <olanglois@sympatico.ca>
and http://www.utm.edu/research/primes/prove/prove2_3.html

Combining these tests to prove primality

Individually these tests are still weak (and again there are infinitely many a-SPRP's for every base a>1 [PSW80]), but we can combine these individual
tests to make powerful tests for small integers n>1 (these tests prove primality):

If n < 1,373,653 is a both 2 and 3-SPRP, then n is prime.
If n < 25,326,001 is a 2, 3 and 5-SPRP, then n is prime.
If n < 25,000,000,000 is a 2, 3, 5 and 7-SPRP, then either n ==
  3,215,031,751 or n is prime. (This is actually true for n < 118,670,087,467.)
If n < 2,152,302,898,747 is a 2, 3, 5, 7 and 11-SPRP, then n is prime.
If n < 3,474,749,660,383 is a 2, 3, 5, 7, 11 and 13-SPRP, then n is prime.
If n < 341,550,071,728,321 is a 2, 3, 5, 7, 11, 13 and 17-SPRP, then n is prime.

The first three of these are due to Pomerance, Selfridge and Wagstaff
[PSW80], the parenthetical remark and all others are due to Jaeschke
[Jaeschke93].  (These and related results are summarized in
[Ribenboim95, Chpt 2viiib].)  In the same article Jaeschke considered
other sets of primes (rather than just the first primes) and found the
slightly better results:

If n < 9,080,191 is a both 31 and 73-SPRP, then n is prime.
If n < 4,759,123,141 is a 2, 7 and 61-SPRP, then n is prime.
If n < 1,000,000,000,000 is a 2, 13, 23, and 1662803-SPRP, then n is prime.

Here is the way we usually use the above results to make a quick
primality test: start by dividing by the first few primes (say those
below 257); then perform strong primality tests base 2, 3, ... until one
of the criteria above is met. For example, if n < 25,326,001 we need
only check bases 2, 3 and 5. This is much faster than trial division
(because someone else has already done much of the work), but will only
work for small numbers (n < 341,550,071,728,321 with the data above).

Numbers printed by this program that are >= 341,550,071,728,321 are
probable primes, but may be composite.

*/


import java.math.BigInteger;
public class FindNextPrime
{
// default constructor
public static BigInteger nextprime(BigInteger n)
  {
  BigInteger result;
//  int idx;
  BigInteger t = BigInteger.valueOf(2L);
  if ( n.compareTo(t) < 0 )	// n < 2
    {
    result = BigInteger.valueOf(2L);
    return result;
    }
  if ( n.compareTo(t) == 0 )	// n == 2
    {
    result = BigInteger.valueOf(3L);
    return result;
    }
//  System.out.println("n<7919=" + (n.compareTo(BigInteger.valueOf(7919L)) < 0) );
  if( n.compareTo(BigInteger.valueOf(7919L)) < 0 )		// n < 7919
    {
    result = BigInteger.valueOf(
	((long) (PrimeTable.findUpperIdx((int) (n.longValue()), 0, 999))));
    return result;
    }

  while(true)
    {
    if ( (n.and(BigInteger.valueOf(1L))).equals(BigInteger.valueOf(0L)) ) // (n & 1) == 0
      n = n.add(BigInteger.valueOf(1L));			// n++;
    else
      n = n.add(BigInteger.valueOf(2L));				// n += 2;

    if ( n.compareTo(BigInteger.valueOf(3215031751L)) == 0 )
      continue;	// n == 3215031751, 3215031751 is composite

    if ( B_SPRP.b_SPRP(n, 2) && B_SPRP.b_SPRP(n, 3) )
      {
      if ( n.compareTo(BigInteger.valueOf(1373653)) < 0)	// ( n < 1373653 )
	{
	return n;
	}
      if ( B_SPRP.b_SPRP(n, 5) )
	{
	if (n.compareTo(BigInteger.valueOf( 25326001 )) < 0)	//( n < 25326001 )
	  return n;
	if ( B_SPRP.b_SPRP(n, 7) )
	  {
	  if (n.compareTo(BigInteger.valueOf(118670087467L)) < 0) //( n < 118670087467L )
	    return n;
	  if ( B_SPRP.b_SPRP(n, 11) )
	    {
	    if (n.compareTo(BigInteger.valueOf(2152302898747L)) < 0) //( n<2152302898747L)
	      return n;
	    if ( B_SPRP.b_SPRP(n, 13) )
	      {
	      if (n.compareTo(BigInteger.valueOf(3474749660383L)) < 0) //(n<3474749660383L)
		return n;
	      if ( B_SPRP.b_SPRP(n, 17) )
		{
		if ( n.compareTo(BigInteger.valueOf(341550071728321L)) == 0 )
		  continue;	// n == 341550071728321 is composite
//		if (n.compareTo(BigInteger.valueOf(341550071728321L)) > 0) //( n >= 341550071728321L )
		if (n.compareTo(BigInteger.valueOf(341550096675653L)) > 0) //( n >= 341550096675653L)
		  System.out.println(n.toString() + " is a probable prime.");
		return n;
		}
	      }
	    }
	  }
	}
      }
    }
  }
}