Mersenne Prime Calculator! Impossibly Simple:

[spiceuvlife]

So I was thinking about Mersenne primes today and started kind of obsessing with them, and decided to save myself a ton of hand work and make a simple python script that would calculate any primes in a set amount of squares of 2.

In case you don't know what a Mersenne prime is, not too many people do, it's a prime number that is found from a square of two, 2^2=4,2^3=8,2^4=16 etc. and then subtracting one from those. For example in 2^3=8 if you subtract one from 8 you get 7, and seven is prime, it's a Mersenne prime. But with 2^4=16, 16-1=15 which is not prime, therefor not a Mersenne prime either. The trick to these is seeing how high a Mersenne prime you can get, and there are 47 as of today. Check out GIMPS and mersenne.org for more information.

So to the code: using a basic prime finding algorithm and a bunch of for loops and an if loop I made the program. Here it is.


for x in range(25):
y=(2**x)-1
prime = True
for divisor in range(2,y):
if y/divisor==int(y/divisor):
prime = False
if prime==False:
print(y)
else:
print(y,"PRIME")

As simple and sweet as anything, and by the way if you're not looking for a ton of waiting I wouldn't suggest going past maybe 30 in your range, because they start to take time. Custom ranges and such can be used. I'm thinking about only trying prime numbers because all the squares are prime and that would majorly cut down on time, but hey it's a good start. Will continue to make improvements, and I'm open to suggestions on fixings.

[Peter_B]

A standard improvement when looking for primes is to only look for factors up to the square root of the number. I've highlighted this in red (n.b. I'm assuming this function is named sqrt, as it is in C/C++):

for x in range(25):
    y=(2**x)-1
    prime = True
    for divisor in range(2,sqrt(y)):
        if y/divisor==int(y/divisor):
            prime = False
    if prime==False:
        print(y)
    else:
        print(y,"PRIME")

But the people who look for Mersenne primes use very advanced techniques to do so, so you won't find any new ones this way

[laserlight]

Along the lines of what has already been discussed:

import math
for x in range(2, 30):
    y = 2 ** x - 1
    prime = next(
        (False for divisor in range(2, int(math.sqrt(y))) if y % divisor == 0),
        True,
    )
    if prime:
        print(y, "PRIME")
    else:
        print(y)

Note that the second argument to range is the number of elements, not the max.

[BioPhysEngr]

Note that the second argument to range is the number of elements, not the max.

I don't think that is correct. See the second example at http://docs.python.org/2/library/functions.html#range . Range(1,11) produces a list with ten elements: the integers between 1 and 10, inclusive.

I think the second argument to range is the (exclusive) maximum.

[laserlight]

Yes, my mistake.