# Mersenne Primes

I saw an interesting challenge on SoloLearn about writing code to find all the Mersenne primes up to a number.  I started by writing a function to test to see if the given number was a prime.

""" A function to test if a given number, input, is prime or not
function returns True or False
"""

def primeTest(input):
factorList = []
for x in range (1,input+1):
if input % x == 0:
factorList.append(x)
if len(factorList)== 2:
return True
else:
return False

It is not perhaps the most elegant solution, but it appears to be fully functional.
I then moved on, using my function above to test to see if a given input was a Mersenne Prime.

""" Function that tests if input is prime or not.
If it is a prime the number is tested to see if it is a mersenne prime.
Function returns True or False
"""

def mersennePrimeTest(input):
if primeTest(input) == False:
return False
else:
powerOfTwo = input + 1
index = log(powerOfTwo,2)
if index % 1 == 0:
return True
else:
return False

I then put these together and produced this code to test all the numbers between 1 and 10000 to see if they were Mersenne Primes.

""" Function that tests all the numbers up to max
to see if they are a Mersenne prime
Function returns a list of Mersenne primes.
"""

def findAllMersennePrimesUpto(max):
primeList = []
for x in range(1,max+1):
if mersennePrimeTest(x)== True:
primeList.append(x)
print(primeList)

The above code works, but it not particularly efficient and it is doing a lot of work that is redundant. I decided to change my approach and to check all the 2n-1 which were below the value of max.

""" Function to test all values of 2^n-1 up to the value of max
"""

def findMersennePrimes(max):
maxIndex = int(log(max,2))
workingnumber = 1
primeList = []
for x in range (maxIndex):
workingnumber = workingnumber * 2
if primeTest(workingnumber-1) == True:
primeList.append(workingnumber-1)
print(primeList)

I found that this version was much faster.

Share

#### You may also like...

This site uses Akismet to reduce spam. Learn how your comment data is processed.