-
February 15th, 2012, 06:31 PM
#1
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.
-
February 15th, 2012, 07:22 PM
#2
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
-
February 17th, 2012, 12:20 PM
#3
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 % 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.
-
January 15th, 2013, 12:00 AM
#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.
Best Regards,
BioPhysEngr
http://blog.biophysengr.net
--
All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.
-
January 15th, 2013, 11:14 PM
#5
Re: Mersenne Prime Calculator! Impossibly Simple:
Tags for this Thread
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|