Skip to content

Instantly share code, notes, and snippets.

@juanplopes

juanplopes/mersenne.py

Created September 16, 2014 19:00
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 juanplopes/5757bbcf47e956361cb7 to your computer and use it in GitHub Desktop.
Save juanplopes/5757bbcf47e956361cb7 to your computer and use it in GitHub Desktop.
Download ZIP
Finding Mersenne Primes using Lucas Lehmer method
Raw
mersenne.py
def prime(n):
return all(n%i!=0 for i in xrange(2,int(n**0.5)+1))
def lucas_lehmer(p):
return reduce(lambda s, _: (s*s-2)%(2**p-1), xrange(p-2), 4)==0
for i in range(2, 2048):
if prime(i) and lucas_lehmer(i):
print '2**%d-1 is a Mersenne prime' % i
print 2**i-1
print '---'
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment