Find Mersenne Prime Numbers Using List Comprehensions And My Code

I wrote this code to find prime numbers, but how could I change it to find Mersenne prime numbers? def prime_test_list(n,known_primes): k = 1 stop_val = len(known_primes) if(n>2

Solution 1:

Something like this:

def mersenne_test(n):

    k =0
    m = 0while m<=n:
        m = 2**k-1if(n==m):
            return"This number is a Mersenne number since it is equal by to 2**%d-1" % k
        k += 1return"This number is not a Mersenne number."

Solution 2:

We can use your prime code as part of finding Mersenee primes. First step, clean up your code:

defprime_test_list(n, known_primes):
    if n < 2:
        returnFalseif n % 2 == 0:
        return n == 2# 2 is the only even prime

    k = 0while known_primes[k] ** 2 <= n:

        if n % known_primes[k] == 0:
            returnFalse

        k += 1returnTruedefprime_print_list(a):
    known_primes = [2]

    for n inrange(3, a, 2):
        if prime_test_list(n, known_primes):
            known_primes.append(n)

    return known_primes

print(prime_print_list(100))

OUTPUT

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

The prime_print_list(n) function returns all the primes less than n. Now we need to add one function and extend prime_print_list(). I'm using Python 3, but it should work in Python 2.

The function we need to add is a Lucas-Lehmer primality test which we call after we've used our existing prime_test_list() function to check an exponent for primeness.

We'll extend prime_print_list() to become mersenne_prime_print_list(() by letting it do what it did, but then perform the above test and keep track of positive results in a separate list:

deflucas_lehmer_test(p, m):
    s = 4for _ inrange(p - 2):
        s = ((s * s) - 2) % m

    return s == 0defprime_test_list(n, known_primes):
    if n < 2:
        returnFalseif n % 2 == 0:
        return n == 2# 2 is the only even prime

    k = 0while known_primes[k] ** 2 <= n:

        if n % known_primes[k] == 0:
            returnFalse

        k += 1returnTruedefmersenne_prime_print_list(a):
    known_primes = [2]
    known_mersenne_primes = [3]

    for n inrange(3, a, 2):
        if prime_test_list(n, known_primes):
            known_primes.append(n)

            m = 2 ** n - 1if lucas_lehmer_test(n, m):
                known_mersenne_primes.append(m)

    return known_mersenne_primes

print(mersenne_prime_print_list(100))

OUTPUT

[3, 7, 31, 127, 8191, 131071, 524287, 2147483647, 2305843009213693951, 618970019642690137449562111]

The mersenne_prime_print_list(n) function returns all the mersenne primes that have prime exponents of less than n.

Of the roughly 50 known Mersenne primes, the above code won't get you much past the 20th or so (mersenne_prime_print_list(5000)) before it becomes too inefficient.

As far as list comprehensions, they aren't needed, but feel free to rewrite the code to use them.

Solution 3:

I haven't tested it, but maybe this would work?

k = 1while k<n:
    if( pow( 2, k) - 1 == n):
        print"This number is a mersenne prime"breakif( pow( 2, k) >= n):
        print"This number is not a mersenne prime"breakelse:
        k+=1

It goes through all of the mersenne primes until it either finds a match with the given number or until the square gets bigger than the given number.