Pages

Project Euler #7 with Python: 10001st Prime Number

For this exercise, one must find the 10001st prime number. The following is my code:

def is_prime(n):
    #if n < 2: return False
    #if n == 2: return True
    #if n & 1: return False
    for i in range(3,int(n**.5)+1,2):
        if not n%i:
            return False
    return True
def prime_list(n):
    primes = [2,3,5,7,11,13]
    i = max(primes) + 2
    while len(primes) < n:
        if is_prime(i):
            primes.append(i)
        i+=2
    return primes
print max(prime_list(10001))

Notice that in the is_prime function, I have made it faster by removing tests that will not be necessary for the range it is working with. Un-comment those lines, and one will notice significant slow-downs.

I can comment out these lines in my primality test, because I am:
  1. not testing primality of numbers less than two
  2. not testing two at all
  3. not testing any even numbers
I just need to optimize and get rid of the doubly nested loops.

EDIT:

After doing some research, I found this awesome prime number generator:

def gen_primes():
    D = {}  
    q = 2  
    while True:
        if q not in D: 
            yield q        
            D[q * q] = [q]
        else:
            for p in D[q]:
                D.setdefault(p + q, []).append(p)
            del D[q]
        q += 1

With this is play, here is my new answer:
def nth_prime(n):
    return (j for i,j in enumerate(gen_primes()) if i == n-1).next()

0 comments:

Post a Comment