prime number generator taking too much time [closed]

Question

I'm solving the problem:

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
What is the 10 001st prime number?

def checkPrime(x):
    facs = 0
    for i in range(1,x):
        if x%i==0:
            facs = facs + 1
    if facs == 2:
        return True
    else :
        return False

i = 1
noPrime = 0
done = False
while(done==False):
    i = i + 1
    print "i = {0} and noPrime={1}".format(i,noPrime)
    if checkPrime(i)==True:
        noPrime = noPrime + 1
        if noPrime==10001 :
            print i
            done=True

But it is taking a lot of time.
How can I speed it up?

Answer 1

A way to do it by using a primality test:

def isPrime(n):
    if n == 2: return True
    if n % 2 == 0 or n < 2: return False
    for i in range(3, int(n**0.5)+1, 2):
        if n % i == 0: return False
    return True
if __name__ == "__main__":
    n = count = 1
    while count < 10001:
        n += 2
        if isPrime(n): count += 1
    print n

Runs in 0.2 seconds. Doesn't matter for this problem but, as others have said, sieve is more efficient.

Answer 2

You can use the prime number theorem to get a pretty good estimate on how far you have to go. (Estimate on the size of the array p in the program). pi(n), the number of primes less than n, is asymptotically n%^.n (n divided by ln n). For the 10001-th prime, the equation is 10001=n%^.n, and solving for n you get that n is between 1.1e5 and 1.2e5.

So, you can reduce the range of the checked values and check the number only of the range. This technique reduces the operating time of the program.