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

Leave a Reply

Your email address will not be published.

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