Time consuming prime number generator

Question

I solve the problem:

After listing the first six primes: 2, 3, 5, 7, 11, and 13, we see that the 6th is 13. What is a 10 001st prime?

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 takes a lot of time.
How can I speed it up?

Answer 1

A way to do this using a primitive 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 

It works after 0.2 seconds. It does not matter for this problem, but as others have said, a sieve is more efficient.

Answer 2

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

Thus, you can reduce the range of checked values ​​and check only the range number. This method reduces program runtime.

Answer 3

You do not need to use Sieve of Eratosthenes for this (although you will be in future problems). Searching for 10001 prime is relatively quick.

Notes:

• Check odd numbers (except # 2)
• You need to check only the divisors to the square root of the value.

Spoiler Below - Assuming you have solved the problem, but it takes a long time

Example in C # (sorry, don't know python):

 class Program { static bool IsPrime(int value) { if (value == 2) return true; if (value % 2 == 0) return false; // Test for divisors up to the square root of "value", increment by 2. for (int i = 3; i <= Math.Sqrt(value); i += 2) { if (value % i == 0) return false; } return true; } static void Main(string[] args) { int primeCount = 1; // #2 // Test only odd numbers. for (int i = 3; ; i += 2) { if (IsPrime(i)) { primeCount++; if (primeCount == 10001) { Console.WriteLine(i.ToString()); break; } } } Console.ReadLine(); } } 

Answer 4

As everyone else was posting their solutions, I thought I would incorporate some obvious improvements into a simple splitting method:

 def is_prime(nr): if nr < 2: return false if nr < 4: return true if nr % 2 == 0: return false if nr < 9: return true if nr % 3 == 0: return false for i in range(5, int(nr**0.5) + 1, 6): if number % i == 0: return false if number % (i + 2) == 0: return false return true 

This improves the simple solution, eliminating the unnecessary modulo operation.