Lucas-Lehmer test: Difference between revisions

Content deleted Content added

Inline

@@ Line 1,161: / Line 1,161: @@
 <pre> Finding Mersenne primes in M[2..33218]:
  M2 M3 M5 M7 M13 M17 M19 M31 M61 M89 M107 M127 M521 M607 M1279 M2203 M2281 M3217 M4253 M4423 M9689 M9941 M11213 M19937 M21701 M23209</pre>
+=== Faster loop without division ===
+<lang python>def isqrt(n):
+    if n < 0:
+        raise ValueError
+    elif n < 2:
+        return n
+    else:
+        a = 1 << ((1 + n.bit_length()) >> 1)
+        while True:
+            b = (a + n // a) >> 1
+            if b >= a:
+                return a
+            a = b
+def isprime(n):
+    if n < 5:
+        return n == 2 or n == 3
+    elif n%2 == 0:
+        return False
+    else:
+        r = isqrt(n)
+        k = 3
+        while k <= r:
+            if n%k == 0:
+                return False
+            k += 2
+        return True
+def lucas_lehmer_fast(n):
+    if n == 2:
+        return True
+    elif not isprime(n):
+        return False
+    else:
+        m = 2**n - 1
+        s = 4
+        for i in range(2, n):
+            sqr = s*s
+            r = (sqr & m) + (sqr >> n)
+            if r >= m:
+                r -= m
+            s = r - 2
+        return s == 0</lang>
 =={{header|Racket}}==