Question

Hello Guys,
I'm a very beginner in computer science.I have trouble solving this problem--find the 1000th prime. i have tried a lot of time,but can not write working code.
the following is one of the code i tried, still not working, can anyone help me with the finding prime problem? thanks
candidate=3
a=[]
prime=[]
for i in range(2,candidate):
b=candidate%i
c=a.append(b)
if 0 in c:
candidate+=2
else:
final_prime=prime.append(candidate)
candidate+=2
while len(final_prime)=999:
Final_prime=[2]+final_prime
print Final_prime

Answer 1

Im just as lost as you bro. But even tho its wrong your code has inspired me to think in a different direction so thank you. I think somewhere you need to multiply n**0.5 + 1. I dunno where yet lol but maybe it will help you.

Answer 2

i worked out the code about the prime number, as following:
candidate=3
final_prime=[2]
while len(final_prime)<1000:
result=True
for i in range(2,candidate):
if(candidate%i==0):
result=False
if result==True:
prime=candidate
final_prime.append(prime)
candidate+=2
print final_prime,final_prime[999]

even though it's not perfectly efficient, it worked. if you have more effient way to solve this problem,please sent me the code, thanks.

Answer 3

Nice job getting your code working :)

One thing you could try to get a bit more efficient code is by breaking (using the `break` keyword) from the loop after you set result to False. That way, the number that are higher won't be checked.

Antoher thing you can have a look at is the Sieve of Eratosthenes (see: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes ) and try to implement that in python.

Answer 4

yes,you are right, thank you

Answer 5

here is a prime test that is actually pretty fast: http://dpaste.com/1004316/

Answer 6

thank you

Answer 7

One thing that everybody seems to forget is that any non-prime number can be factored into prime numbers. If you implement that fact, your program will run fast.

Answer 8

what does that even mean rsmith? any non prime number can be factored into prime numbers? how will that make the program run fast?

Answer 9

don't you still have to perform primality tests to generate prime numbers? those tests consume the time.

http://dpaste.com/1010237/

Answer 10

Memoization.

Answer 11

@rsmith6559 - so you are talking about an algorithm that uses previously found primes in the primality tests. do you have an example?

Answer 12

primes = [ 2, 3 ]
testNum = 5
numberOfPrimes = 10000

while( len( primes ) < numberOfPrimes ):
for i in xrange( 0, len( primes ) ):
if( testNum % primes[i] ):
if( i == ( len( primes ) - 1 )):
primes.append( testNum )
else:
break
testNum += 2

Answer 13

@rsmith6559 - the algorithm you posted takes 70 times longer to find the 10,000th prime than one using the test i posted. http://dpaste.com/1011884/

Answer 14

I tuned the code a bit:

primes = [ 2, 3 ]
testNum = 5
numberOfPrimes = 10000

while( len( primes ) < numberOfPrimes ):
for i in xrange( 0, len( primes ) ):
if( testNum % primes[i] ):
if( primes[i] * primes[i] > testNum ):
primes.append( testNum )
break
else:
break
testNum += 2


I'm getting 0.67 second execution time.

Answer 15

still 20% slower
http://dpaste.com/1012984/

Answer 16

I don't see how you can be getting 20 second times:

[zeus@stamRSMITH:~/Desktop]$ time ./ps1.py
The 10000th prime is: 104729

real 0m0.688s
user 0m0.662s
sys 0m0.017s
[zeus@stamRSMITH:~/Desktop]$ time ./ps1.py
The 10000th prime is: 104729

real 0m0.674s
user 0m0.656s
sys 0m0.016s
[zeus@stamRSMITH:~/Desktop]$ time ./ps1.py
The 10000th prime is: 104729

real 0m0.676s
user 0m0.657s
sys 0m0.016s
[zeus@stamRSMITH:~/Desktop]$ time ./ps1.py
The 10000th prime is: 104729

real 0m0.678s
user 0m0.657s
sys 0m0.016s
[zeus@stamRSMITH:~/Desktop]$ time ./ps1.py
The 10000th prime is: 104729

real 0m0.679s
user 0m0.659s
sys 0m0.017s
[zeus@stamRSMITH:~/Desktop]$ time ./ps1.py
The 10000th prime is: 104729

real 0m0.674s
user 0m0.656s
sys 0m0.016s

Answer 17

http://docs.python.org/2.7/library/timeit.html

those times are for 100 executions - finding the 10000th prime 100 times

on my machine your algorithm takes 25. seconds for 100 executions - which is still 20% slower than the algorithm from the wikipedia article.

i made a couple of readability changes to your code at lines 7, 8, 9 - http://dpaste.com/1013998/

now yours is 25% faster - cool

Answer 18

I'm not saying that my code is the fastest possible. Originally, I was just commenting on a mathmatical fact that nobody was taking advantage of. My purpose for mentioning it was that the brute force algorithms, with thought, could be replaced with more efficient algorithms. Certainly a lesson to be taken from ps1 (Problem Set 1).