Project Euler: Problem 7

My new math trick of the day? Upper and lower bounds on the nth prime:

n * ln(n) + n * ln(ln(n - 1)) is less than p[n] is less than n * ln(n) + n * ln(ln(n)) for n greater than or equal to 6

Using this little nugget, I can give myself an upper bound on the numbers I need to test for primality and unleash the Sieve of Eratosthenes on Problem 7. BTW, I realize the Sieve isn't the most performant way to do most of these tests; I just think it's a really elegant solution for finding primes and it isn't slow enough to be an issue for most numbers of this size. At any rate, here's my script:

"""Solves Problem 7 from Project Euler."""

import math

FIRST_SIX_PRIMES = {1:2, 2:3, 3:5, 4:7, 5:11, 6:13}

def e_sieve(upper_bound):
    """Uses the Sieve of Eratosthenes to get a list of the primes up to max."""
    primes = []
    candidates = range(2, upper_bound)
    while candidates:
        head = candidates[0]
        candidates = [n for n in candidates[1:] if n % head]

    return primes

def problem_7(n):
    """Finds the nth prime number.

    Thanks to
    we know that it will be less than n * ln(n) + n * ln(ln(n))
    (for n >= 6).
    if n < 6:
        return FIRST_SIX_PRIMES[n]

    upper_bound = int(n * math.log(n) + n * math.log(math.log(n)))

    primes = e_sieve(upper_bound)
    return primes[n - 1]

if __name__ == '__main__':
    print problem_7(10001)

Back to flipping out...

blog comments powered by Disqus