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
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
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)
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)
"""
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.
