prime number generator taking too much time [closed]

Question

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.

Closed 9 years ago.

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.

Answer 3

You don't need to use Sieve of Eratosthenes for this (although you will in future problems). Finding the 10001 prime is relatively quick.

Things to note:

• Only test odd numbers (except #2)
• You only have to test for divisors up to the square root of the value.

Spoiler Below - Assuming you have solved the problem but it just 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

Since everybody else was posting their solutions, I thought I'd include some obvious improvements to the simple divide 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 upon the simple solution by getting rid of one unnecessary modulo operation.