Skip to content

Instantly share code, notes, and snippets.

@st0le

st0le/Lucas Lehmer Primality Test

Last active December 16, 2015 17:40
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save st0le/5472016 to your computer and use it in GitHub Desktop.
Save st0le/5472016 to your computer and use it in GitHub Desktop.
Download ZIP
Lucas Lehmer Primality Test
Raw
Lucas Lehmer Primality Test
def lucasLehmerTest(p): #checks if 2^p - 1 is a prime (also called a mersenne prime)
if p % 2 == 0 and not isPrime(p): return False
s = 4
M = (1 << p) - 1
for _ in xrange(p - 2):
s = ((s * s) - 2) % M
return s == 0
def isPrime(n):
if n <= 3 or n % 2 == 0 or n % 3 == 0: return n == 2 or n == 3
for i in xrange(5, int(n**0.5)+1, 6):
if n % i == 0 or n % (i + 2) == 0:
return False
return True
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment