prime number generator taking too much time

prime-factoring, python

Solution

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.

Problem

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?

Original source