//Implementación del método de Lucas-Lehmer para calcular
//números primos de la forma 2^n - 1 (primos de Mersenne)
//v 1.09 - 2006-01-07
//Programado por: José Ángel González Rodríguez
//

import java.math.BigInteger;
import java.io.*;

class LucasLehmerInput {

	static double start_time = System.currentTimeMillis();

	static double time_elapsed;

	static int np;
	
	static int pnum;
	
	private static BufferedReader stdin = new BufferedReader( 
	        new InputStreamReader( System.in ) );
	

	public static void main(String args[])  throws IOException {
		while (true) {
			np = 0;
			System.out.print( "Introduzca el exponente primo (por ejemplo 607): " );
			String input = stdin.readLine();
			pnum = Integer.parseInt(input);
			start_time = System.currentTimeMillis();
			escribePrimosMersenne();
			time_elapsed = System.currentTimeMillis() - start_time;
			System.out.println("");
			System.out.println(np + " primos de Mersenne por el método de "
					+ "Lucas-Lehmer");
			System.out.println("Tiempo: " + time_elapsed / 1000 + " seg");
			System.out.println("");
		}
	}

	static int esPrimo(int n) {
		int rq = (int) Math.sqrt(n);
		for (int i = 2; i <= rq; i++) {
			if (n % i == 0)  {
				System.out.println(n + " no es primo");
				return 0;
			}
				
		}
		System.out.println(n + " es primo");
		return n;
	}

	static void escribePrimosMersenne() {
		int n = esPrimo(pnum);
		if (n != 0) {
			BigInteger Mp = BigInteger.valueOf(2).pow(n);
			Mp = Mp.add(BigInteger.valueOf(-1));
			BigInteger s = BigInteger.valueOf(4);
			for (int j = 2; j < n; j++) {
				s = s.pow(2);
				s = s.add(BigInteger.valueOf(-2));
				s = s.mod(Mp);
				if (s.equals(BigInteger.valueOf(0))) {
					np++;
					System.out.println("");
					System.out.println("M" + n + " es primo");
					System.out.println("p=" + n + " M" + n + "=2^" + n
							+ "-1=" + Mp + " S" + j + "=" + s);
					break;
				}
			}
		}
	}
}