Finding specific prime number [closed]

StackOverflow https://stackoverflow.com/questions/22364619

  •  13-06-2023
  •  | 
  •  

Question

Here is my implementation of finding a specific prime number:

import math

def checkPrime(i):
    if i == 3:
        return True;
    elif i == 2:
        return True;
    else:
        count = 2;
        prime = 2;
        
        while count <= math.sqrt(i):
            if (i % count == 0):
                prime += 1;
            count += 1;

        if prime == 2:
            return True;
        else:
            return False;

x = 0;
c = 2;
while x < 10001:
    if checkPrime(c) == True:
        print c;
        x += 1;
    c += 1;

I used this to find the 10,001st prime number (A problem I took from Project Euclid). However, this doesn't seem to me to be an efficient way of solving the problem. It takes up a lot of computing power (evident from the fact that it takes around 20 seconds to finish executing). I solved this on my own, but the amount of time it takes is daunting.

What would be the most efficient way of accomplishing this problem?

P.S: I am printing out all the prime numbers to keep just see the out as a preference. It is not needed.

Was it helpful?

Solution 

def fast_primes(max_n):
    numbers = range(3, max_n+1, 2)
    half = (max_n)//2
    initial = 4

    for step in xrange(3, max_n+1, 2):
        for i in xrange(initial, half, step):
            numbers[i-1] = 0
        initial += 2*(step+1)

        if initial > half:
            return [2] + filter(None, numbers)
start = 5
tmp = []
while len(tmp) <  10001:
    tmp=fast_primes(start)
    start <<=1

print tmp[10001]

seems to be pretty fast to me (took 0.02 seconds on my marginal computer)

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top