Real Ultimate Programming

The Home for People Who Like to Flip Out and Write Code

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. Yes, 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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
    """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]
            primes.append(head)
            candidates = [n for n in candidates[1:] if n % head]

        return primes

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

        Thanks to
        http://en.wikipedia.org/wiki/Prime_number_theorem#Approximations_for_the_nth_prime_number
        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…