Question

Are there faster methods for calculating primes? If so, what are they?

Answer 1

The standard method, of course, checks for a given number n whether n is divisible by all integers between 2 and n-1. A faster algorithm checks to see only integers between 2 and \[\sqrt{n}\]. This second method is considerably faster than the first, though still impractical for very large primes. I provide functions for each:

def primetest1(test_num):
if test_num%2==0:
return False
for i in range (2, test_num):
if test_num%i==0:
return(False)
return(True)


def primetest2(test_num):
if test_num%2==0:
return False
for i in range (2, int(sqrt(test_num))+1):
if test_num%i==0:
return(False)
return(True)

Answer 2

I cleaned up the code a bit. A couple of the lines are redundant. The two functions should look like this:

ef primetest1(test_num):
for i in range (2, test_num):
if test_num%i==0:
return(False)
return(True)


def primetest2(test_num):
for i in range (2, int(sqrt(test_num))+1):
if test_num%i==0:
return(False)
return(True)

Answer 3

Here's a complete program that calculates the nth prime (based on your input) using a more efficient algorithm (function primetest2). It's considerably faster than the standard technique.

rom time import *
from math import *

def primetest2(test_num):
for i in range (2, int(sqrt(test_num))+1):
if test_num%i==0:
return(False)
return(True)


def giveNthPrime(search_prime):

count=-1
testNum=1
nthPrime=0

while count<search_prime:
if primetest2(testNum):
count+=1
nthPrime=testNum
testNum+=1
return nthPrime

start = clock()
which_prime=int(raw_input("Which prime are you looking for? "))
end = clock()
time_elapsed = end-start
print which_prime,giveNthPrime(which_prime)
print "It took me: ", time_elapsed

Answer 4

http://en.wikipedia.org/wiki/Prime_number#Testing_primality_and_integer_factorization

Answer 5

My code took 25.6 seconds to compute the 3000th prime. Your code took 1.47 seconds. Congrats. It's fast.

Answer 6

malpaso,
In your complete example aren't you timing the time it takes the user to enter which prime they are looking for and not the time it takes the function to compute that prime?

You start and stop around the call to raw_input and no the call to giveNthPrime.

Just wondering...maybe I read that wrong.

Answer 7

How about this code?

from time import*
start=clock()
import math
number=3
primecounter=2
while(primecounter <= 3000):
divisor=2
divisors_total=0
while(divisor < math.sqrt(number)+0.5):
if(number%divisor==0):
divisors_total=divisors_total+1
divisor=divisor+1
if(divisors_total == 0):
primecounter=primecounter+1
## print number
number=number+2
print number-2
print clock()-start

Answer 8

CrashT,
That will find the 3000th prime. You can make it more efficient if you stop testing the possible prime number when you find a divisor that gives you a remainder of 0.

Also, why do you add .5 to the square root of the prime you are trying to test?

Answer 9

I believe it gives the wrong answer if it is not included due to the nature of the test.

Also, I tested both my code and malpaso's... his seems to still be quite a bit faster. approx, 0.1s for his code and 0.4 seconds for mine

Answer 10

Mateo2. Nice pick up. You are absolutely correct. I have been working with so many different versions of the code that I put the timers in the wrong place. Here is the corrected version.

from time import *
from math import *

def primetest2(test_num):
for i in range (2, int(sqrt(test_num))+1):
if test_num%i==0:
return(False)
return(True)


def giveNthPrime(search_prime):

count=-1
testNum=1
nthPrime=0

while count<search_prime:
if primetest2(testNum):
count+=1
nthPrime=testNum
testNum+=1
return nthPrime


which_prime=int(raw_input("Which prime are you looking for? "))

start = clock()
print which_prime,giveNthPrime(which_prime)
end = clock()
time_elapsed = end - start
print "It took me: ", time_elapsed

Answer 11

BTW. I tried to find the 100008th Prime and it took approximately 23 seconds.

Which prime are you looking for? 100008
100008 1299827
It took me: 22.851086

Answer 12

malpaso, i noticed the timer too... i just turned off the whole input and placed the timer's in the locations I felt were representative. it seems like a pretty good code otherwise.


Does anyone know how to copy and paste the text from these effectively?

Answer 13

Here is my function for figuring out if a number is prime. I first check if p is 2, return true if it is. Check to see if the number is even, return false if it is. Try to divide by all the odds between 3 and the square root of p. (I added 1 to sqrt(p) because range goes up to, but not including the number you pass it for end.) Return false the first time a divisor divides evenly into p. Return true if we never returned false. It's messy...

def isprime(p):
if p == 2: # 2 is the first prime number.
return True
if p%2 == 0:
return False

highest = int(sqrt(p)) + 1 # biggest value we need to divide by + 1.
# find all odds from 1 to sqrt(p)
divisors = range(3, highest, 2)
# print "Divisors: ", divisors
for x in divisors:
if p % x == 0:
# Not prime.
return False
return True

Answer 14

CrashT, the easiest way I've found so far is to highlight what i want to copy, right click, view source. It preserves the spacing/tabs but eats the < > signs. Just do a find/replace in any editor to fix. ***This probably only works in firefox.

Answer 15

I tried 100008 and it was taking awhile for my code. Here are the results for 10000 instead. The result on the bottom is yours


104729
4.29341525333
>>> ================================ RESTART ================================
>>>
10000 104729
It took me: 0.445085866667

Answer 16

thanks mateo. that worked great in firefox. no find/replace necessary

Answer 17

I might be wrong on this, but i *think* you could make it even faster if you only try to divide by all the primes less than the square root of the number you're testing. Since you are calculating them all anyway, you could save them off into a list and use that list instead of the range function.

Answer 18

i was thinking the same kind of thing, but i am having a hard time thinking about how to implement that. right now, i think the most efficient code I can think of would only test to see if the number is divisible by only the primes that are less than or equal to the number's square root.

Answer 19

I don't know precisely how it does it, but when I type Prime[100000] into Mathematica, it returns 1299709 almost instantly...

The following "calculation" in Mathematica takes about 5 seconds
In[1]:= Prime[100000000000]
Out[1]= 2760727302517

Answer 20

This is what I got... after a whole bunch of hours staring at the screen...
def topprime(x):
if x == 1:
print 2
else:
z = 3
ctr = 1
while ctr<=x:
n = 2
while z%n !=0 :
n = n + 1
if n == z:
ctr = ctr + 1
if ctr == x:
print z
z = z + 1


>>> def Lesson_1():
x = input('Type the Nth prime number you would like to see: ')
topprime(x)

Answer 21

The time it took on my computer is shown below. I think it can be more efficient.

>>> topprime(10000)
104729
39.0525252267

Answer 22

If you use the sqrt method the algorithm takes less than a second to arrive at the 10000th prime..

Which prime number do you want? 10000
10000 104729
It took me: 0.666207

Answer 23

And it takes approximately 23 seconds to calculate the 100,008th prime.

Which prime number do you want? 100008
100008 1299827
It took me: 23.074645

Answer 24

I found another approach (algorithm) where you can arrive at the 100,008th prime in a little over 10 seconds. I will describe it later. Basic idea is to use a known set of beginning prime numbers as the divisor.

Which prime number do you want? 100008
100008 1299827
It took me: 10.391521

Answer 25

I wonder if you can build the list recursively... i will experiment

Answer 26

Appending list concept gives me my best result yet.
100008 th prime number is 1299827
11.6685471289 seconds


code is:

from time import*
start=clock()

from math import*
number=3
nthprime=100008
primecounter=2
L=[2,3]
while(primecounter <= nthprime):
current=0
divisor=L[current]
divisors_total=0
while(divisor < sqrt(number)+0.5 and divisors_total==0):
if(number%divisor==0):
divisors_total=divisors_total+1
current+=1
divisor=L[current]
if(divisors_total == 0):
primecounter=primecounter+1
L.append(number)
number=number+2
print nthprime,"th prime number is ",number-2
print clock()-start,"seconds"

Answer 27

after cleaning up the initial state variables:

100008 th prime number is 1299827
9.03100074667 seconds

Answer 28

from time import*
start=clock()

from math import*

nthprime=100008

assert nthprime!=1,'value must be integer greater than 1'

number=5
prime_ctr=3
L=[3]

while(prime_ctr <= nthprime):
div_ctr=0
div_total=0
while(L[div_ctr] < sqrt(number)+0.01 and div_total==0):
if(number%L[div_ctr]==0):
div_total+=1
div_ctr+=1
if(div_total == 0):
prime_ctr+=1
L.append(number)
number=number+2
print nthprime,"th prime number is ",number-2
print clock()-start,"seconds"

Answer 29

ANOTHER IMPROVEMENT (and probably the last... it's been fun):
This code uses prime number theory, a pre-generated list of large prime numbers as starting points, and other little tricks.

you can use it to calculate the nth prime up to and include the 10,000,000th! My computer takes about 10 seconds to find some of them, max. Others, it takes a fraction of the time.

(see attached)

see if you can figure out the details and let me know what you think!