Lucas-Lehmer test: Difference between revisions

Content added Content deleted

Inline

@@ Line 134: / Line 134: @@
  Mersenne primes:
  M2 M3 M5 M7 M13 M17 M19 M31
+=={{header|Java}}==
+We use arbitrary-precision integers in order to be able to test any arbitrary prime.
+ import java.math.BigInteger;
+ public class Mersenne
+ {
+     public static boolean isPrime(int p) {
+         if (p == 2)
+             return true;
+         else if (p <= 1 || p % 2 == 0)
+             return false;
+         else {
+             int to = (int)Math.sqrt(p);
+             for (int i = 3; i <= to; i += 2)
+                 if (p % i == 0)
+                     return false;
+             return true;
+         }
+     }
+     public static boolean isMersennePrime(int p) {
+         if (p == 2)
+             return true;
+         else {
+             BigInteger m_p = BigInteger.ONE.shiftLeft(p).subtract(BigInteger.ONE);
+             BigInteger s = BigInteger.valueOf(4);
+             for (int i = 3; i <= p; i++)
+                 s = s.multiply(s).subtract(BigInteger.valueOf(2)).mod(m_p);
+             return s.equals(BigInteger.ZERO);
+         }
+     }
+     // an arbitrary upper bound can be given as an argument
+     public static void main(String[] args) {
+         int upb;
+         if (args.length == 0)
+             upb = 500;
+         else
+             upb = Integer.parseInt(args[0]);
+         System.out.println(" Finding Mersenne primes in M[2.." + upb + "]: ");
+         for (int p = 2; p <= upb; p++)
+             if (isPrime(p) && isMersennePrime(p))
+                 System.out.print(" M" + p);
+         System.out.println();
+     }
+ }
+Output:
+ Finding Mersenne primes in M[2..500]:
+ M2 M3 M5 M7 M13 M17 M19 M31 M61 M89 M107 M127