/* Lucas-Lehmer test for primality of
   Mersenne numbers  2^p-1  where p must
   be prime for the number to be prime */

import java.math.BigInteger;

public class lucaslehmer {

public static void main(String args[]) {
 BigInteger zero=new BigInteger("0") ;
 BigInteger one =new BigInteger("1") ;
 BigInteger two =new BigInteger("2") ;

 int p1 = Integer.parseInt(args[0]) ;  // get command-line exponent  
 int p2 = p1;

 if(p1%2 == 0) { 
  System.out.println("--- Exponents must be odd ----") ;
  System.exit(0) ;
  }

 if(args.length==2)
  p2 = Integer.parseInt(args[1]) ;

 for(int p=p1; p<=p2; p+=2) {  //only use odd exponents.
  BigInteger mersenne = two.pow(p).subtract(one) ;

  BigInteger lucas = new BigInteger("4") ;  //initialize
   for(int i=3; i<=p; i++)
    lucas = lucas.pow(2).subtract(two).mod(mersenne) ;

  if(lucas.compareTo(zero) == 0)
   System.out.println("***** 2^"+p+"-1  is prime *****") ;
    else
   System.out.println(" 2^"+p+"-1  is composite.") ;
 } 
}

}