import java.math.BigInteger;

// use the BigInteger class to determine Mersenne primes (a Mersenne prime is a value i such that 2^i - 1 is a prime number
// since 2^i may be very large, say for i = 50, we need to use BigInteger instead of int or long

public class Prog10_19
{
	public static void main(String[] args)
	{
		BigInteger j;						// to store each 2^i - 1 value
		for(int i=2;i<30;i++)				// iterate from 2 to 30 to test each i as a Mersenne prime (the book calls for 2..100 but that will take too long)
		{
			j = new BigInteger(""+(int)(Math.pow(2,i)-1));		// create 2^i - 1 as a BigInteger, notice the parameter must be a String and Math.pow returns a double, so we have a couple of casts here!
			if(isPrime(j)) System.out.println(i + " is a Mersenne prime");	// if we find that the BigInteger j is a prime, then i is a Mersenne Prime
		}
			
	}
	
	// this is a typical isPrime method except that it operates on BigIntegers instead of ints
	public static boolean isPrime(BigInteger i)			// we need to use the .remainder method to determine if i has a divisor, and it uses a BigInteger for both numerator and denominator
	{
		BigInteger denom = new BigInteger("2");			// our denominator starts at BigInteger("2")
		boolean foundDivisor = false;					// if we find a divisor, then i is not a prime
		BigInteger k;									// used to store the result of our remainder operation
		BigInteger zero = new BigInteger("0");			// needed to compare our remainder (a BigInteger) to 0
		BigInteger one = new BigInteger("1");			// used to increment our divisor
		while(!foundDivisor&&denom.compareTo(i)<0)		// iterate until either BigInteger denom equals i, or we find a divisor, notice since denom & i are BigIntegers, we need to compare them using .compareTo
		{
			k=i.remainder(denom);						// compute the remainder, that is, k = i%denom except that k, i, and denom are BigIntegers
			if(k.compareTo(zero)==0) foundDivisor=true;		// compare the remainder, k, to 0, but k is a BigInteger so we have to compare it to BigInteger("0"), if they equal, then denom is a divisor and i is not prime
			else denom = denom.add(one);				// otherwise, we increment denom but since denom is a BigInteger, we have to increment it using the .add method where the parameter is a BigInteger("1")
		}
		return foundDivisor;
	}
}