05.30.08

Project Euler: Problem 7

Posted in python tagged , , at 4:00 pm by redochre

Problem 7:

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 10001st prime number?

A solution:

import math

def isPrime(num):
    if type(num) != int: return False
    if num == 2: return True
    if num < 2 or num % 2 == 0: return False
    return not any(num % i == 0 for i in range(3, int(math.sqrt(num))+1, 2))

n = 10001
count_of_found = 2 # assuming 2 and 3 to start
current_number = 3
current_prime = 3
while count_of_found < n:
    current_number += 2
    if isPrime(current_number):
        current_prime = current_number
        count_of_found += 1

print 'nth prime for n=%d is %s' % (n, current_prime)

This problem was originally solved with a factorize function written for a previous problem, checking primality by looking at the number of factors. This way is faster. Plus, it’s good “generator expression” practice. :)

6 Comments »

  1. parseidon said,

    7 June, 2008 at 1:03 pm

    This bit of code I came with seems to accomplish the same job, but a little bit faster (1.07s vs. 0.5s for 10001st):

    def getNthPrime(nth):

    …i, primes = 3, [2,3]

    ……while len(primes) < nth:

    ……:..prime = True

    ……:..for x in range (int(math.sqrt(len(primes)))+1):
    ……:..:..if i%primes[x] == 0:

    ……:..:..:..prime = False
    ……:..:..:..break

    ……:..if prime == True:

    ……:..:..primes.append(i)

    ……:..i+=2

    …return primes

    print getNthPrime(10001)[-1]

    although the syntax is much uglier.

  2. redochre said,

    7 June, 2008 at 3:01 pm

    The line
    for x in range(int(math.sqrt(len(primes)))+1)
    isn’t quite right. The check that involves the square root is based on the fact that for any composite number n, n will have at least one prime factor math.sqrt(i): break
    …. (the rest of what you’ve got)

    I’m not quite sure when your version will go wrong, but I think there is a point when it’ll break because that check isn’t quite right.

  3. parseidon said,

    7 June, 2008 at 3:24 pm

    Yeah, I know. I’ve found there seemed to be a correlation at that precise point, but again, I thought that having it going from the st to millionth prime (15485863) without failing was a good enough proof for me.

    As it doesn’t seem to rely on recursion, it sounds like there would be a direct correlation between the position of the prime in the list and the current number. I don’t know, I’m under the [possibly wrong] impression that if there was a problem with the square-rooting, it would appear more apparent as numbers get bigger.

    I’m wondering if it would break before the limit of range(), if it’s not right. So far it got up to the millionth prime right, and I’m not quite sure if I’ll test more as it took a bit over 10 minutes to do that one.

  4. redochre said,

    11 June, 2008 at 7:36 am

    Hm, there must be some deeper math going on there that I don’t understand, I guess.

  5. Kadhirvel said,

    29 July, 2008 at 10:54 am

    Please follow the link below for fact about primes

    http://kadiprimality.blogspot.com/

  6. jimmy said,

    2 June, 2009 at 9:27 am

    Even faster solution.

    def list_of_primes(n):
    primes =[]
    n_factors = [0]*n
    for i in range(2,n):
    if n_factors[i] == 0:
    primes.append(i)
    n_factors[i*2:n:i] = [1]*((n-1)/i-1)
    if len(primes) == 10001:
    return primes
    print list_of_primes(1000000)[10000]


Leave a Comment