Looking for something else?

Not the answer you are looking for? Search for more explanations.

## More answers

Looking for something else?

Not the answer you are looking for? Search for more explanations.

- anonymous

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

At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga.
Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus.
Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.

Get our expert's

answer on brainly

SEE EXPERT ANSWER

Get your **free** account and access **expert** answers to this

and **thousands** of other questions.

Get your **free** account and access **expert** answers to this and **thousands** of other questions

- anonymous

- schrodinger

I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!

Get this expert

answer on brainly

SEE EXPERT ANSWER

Get your **free** account and access **expert** answers to this

and **thousands** of other questions

- anonymous

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.

- anonymous

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.

- anonymous

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.

Looking for something else?

Not the answer you are looking for? Search for more explanations.

- anonymous

yes,you are right, thank you

- anonymous

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

- anonymous

thank you

- rsmith6559

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.

- anonymous

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

- anonymous

don't you still have to perform primality tests to generate prime numbers? those tests consume the time.
http://dpaste.com/1010237/

- rsmith6559

Memoization.

- anonymous

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

- rsmith6559

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

- anonymous

@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/

- rsmith6559

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.

- anonymous

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

- rsmith6559

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

- anonymous

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

- rsmith6559

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).

Looking for something else?

Not the answer you are looking for? Search for more explanations.