CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

# Thread: Mersenne Prime Calculator! Impossibly Simple:

1. Junior Member Join Date
Oct 2011
Posts
2

## Mersenne Prime Calculator! Impossibly Simple:

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.  Reply With Quote

2. Member +      Join Date
Jan 2009
Posts
596

## Re: Mersenne Prime Calculator! Impossibly Simple:

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++):
Code:
```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   Reply With Quote

3. Elite Member Power Poster           Join Date
Jan 2006
Location
Singapore
Posts
6,768

## Re: Mersenne Prime Calculator! Impossibly Simple:

Along the lines of what has already been discussed:
Code:
```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 &#37; 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.  Reply With Quote

4. ## Re: Mersenne Prime Calculator! Impossibly Simple: Originally Posted by laserlight 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.  Reply With Quote

5. Elite Member Power Poster           Join Date
Jan 2006
Location
Singapore
Posts
6,768

## Re: Mersenne Prime Calculator! Impossibly Simple:

Yes, my mistake.  Reply With Quote

easy, python #### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
• 