Mersenne primes

A Mersenne prime, $M_i$, is a prime number of the form $M_i = 2^i -1$. The set of Mersenne primes less than $n$ may be thought of as the intersection of the set of all primes less than $n$, $P_n$, with the set, $A_n$, of integers satisfying $2^i - 1 < n$.

The following program returns a list of the Mersenne primes less than 1000000.

import math

def primes(n):
    """ Return a list of the prime numbers <= n. """

    sieve = [True] * (n // 2)
    for i in range(3, int(math.sqrt(n))+1, 2):
        if sieve[i//2]:
            sieve[i*i//2::i] = [False] * ((n - i*i - 1) // (2*i) +1)
    return [2] + [2*i+1 for i in range(1, n // 2) if sieve[i]]

n = 1000000

P = set(primes(n))

# A list of integers 2^i-1 <= n 
A = []
for i in range(2, int(math.log(n+1, 2))+1):
    A.append(2**i - 1)

# The set of Mersenne primes as the intersection of P and A
M = P.intersection(A)

# Output as a sorted list of M
print(sorted(list(M)))

The prime numbers are produced in a list by the function primes which implements an optimized version of the Sieve of Eratosthenes algorithm (see Exercise P2.5.8); this is converted into the set, P. We can take the intersection of this set with any iterable object using the intersection method, so there is no need to explicitly convert our second list of integers, A, into a set.

Finally, the set of Mersenne primes we create, M, is an unordered collection, so for output purposes we convert it into a sorted list.

For $n=1000000$, This output is:

[3, 7, 31, 127, 8191, 131071, 524287]