//Implementación del método de Lucas-Lehmer para calcular
//números primos de la forma 2^n - 1 (primos de Mersenne)
//v 1.10 - 2006-01-07
//Programado por: José Ángel González Rodríguez
//En un Pentium a 1133 MHz calcula los 13 primeros primos de Mersenne (aparte de M2)
//en menos de 2 segundos.

import java.math.BigInteger;

class LucasLehmer {

	static double start_time = System.currentTimeMillis();

	static double time_elapsed;

	static int np;

	public static void main(String args[]) {
		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");
	}

	static int esPrimo(int n) {
		int rq = (int) Math.sqrt(n);
		for (int i = 2; i <= rq; i++) {
			if (n % i == 0)
				return 0;
		}
		return n;
	}

	static void escribePrimosMersenne() {
		for (int i = 3; i < 700; i++) {
			int n = esPrimo(i);
			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;
					}
				}
			}
		}
	}
}