Real Ultimate Programming

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

Project Euler: Problem 7, Redux

Remember how I mentioned the Sieve wasn’t the most performant solution)? Here’s a much faster solution. On my system the time dropped from 11.661 seconds to .332 seconds. Also, it makes use of one of my favorite features in Python, so far: generators.

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
35
36
37
38
39
40
41
42
    """Solves Problem 7 from Project Euler."""
    import math
    import sys


    def is_prime(candidate, known_primes):
        """Determines whether candidate is prime by trial division using \
        known_primes.

        For this function to work, known_primes *must* be accurate.
        """
        last_possible = math.sqrt(candidate)
        for current_prime in known_primes:
            if current_prime > last_possible:
                break
            if not candidate % current_prime:
                return False
        return True


    def primes_generator():
        """A generator for all the primes <= sys.maxint."""
        candidates = xrange(2, sys.maxint)
        primes = []
        for n in candidates:
            if is_prime(n, primes):
                primes.append(n)
                yield n


    def problem_7(n):
        """Finds the nth prime number."""
        primes = primes_generator()
        i = 0
        while i < n - 1:
            i += 1
            primes.next()
        return primes.next()


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

Back to flipping out…