Question

What is the complexity of finding the 1000th prime number problem?

Answer 1

I think it is P time.

Answer 2

I just write a function to test if a given number a prime number,then call it in a loop to accumulate it.

Answer 3

right

Answer 4

http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf This paper shows that the complexity is PTIME

Answer 5

so you check every prime number til the 1000th one, then accumulate it?

Answer 6

Actually, I write another two functions.,one is to find the prime number not bigger than 1000,the other one to find the 1000th prime number .
check then count or append it to a list.

Answer 7

There's an efficient algorithm to find prime number not bigger than n: the sieve of eratosthenes (there are other sieves but the sieve of eratosthenes is probably the simplest one and still works very fast): http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Answer 8

Here's a python implementation: http://rosettacode.org/wiki/Sieve_of_Eratosthenes#Python

Answer 9

Try to get people to 'think' about the problem...not get the answer right out!!!