23
\$\begingroup\$

I'm solving Project Euler problem 7, which says:

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?

Here's the code I've written:

def primes(n):
    primes = []
    attempt = 3
    while len(primes) < (n-1):
        for i in range(len(primes)):
            if attempt % primes[i] == 0:
                attempt += 2
                break
        else:
            primes.append(attempt)
            print (primes)
    return (primes)

While testing a number, if it finds that the number is divisible by one of the primes in the list, the for loop breaks, and starts again with a larger number. If it isn't divisible, it's added to the list of primes. This keeps going until the list is as large as desired (in this case 10000, and I've omitted 2 so the last member of the list is the 10001st prime)

The problem is that this is extremely slow. I've seen other solutions that can apparently solve this in seconds, if not less. What are some ways I could make this run faster?

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Welcome to Code Review! There's a recent question about finding the sum of primes here that might help a little even though their aim was different. \$\endgroup\$ Sep 1, 2015 at 14:32
  • 4
    \$\begingroup\$ Whenever you solve a problem on Project Euler you gain access to a document presenting official solutions to the problem, check the main page where your problem is found. \$\endgroup\$
    – user29120
    Sep 1, 2015 at 14:59
  • \$\begingroup\$ You might try if not attempt % primes[i] rather than comparing to 0. I wonder if negating is faster than comparing to 0 or if it's a draw? \$\endgroup\$
    – sunny
    Sep 1, 2015 at 21:04

5 Answers 5

14
\$\begingroup\$

First off, don't print every single loop. It's wasteful and surprisingly intensive. Also, you don't need to return all primes, your brief only requires one. You should make it more clear what the function is for. Return the last found prime, probably also rename your function to prime.

Don't omit 2, it's only a strange and confusing work around that you haven't even explained in the code. Just include it in the initialisation of primes.

primes = [2]

Also you don't need to do

for i in range(len(primes)):
    if attempt % primes[i] == 0:

Python has a simpler for var in iterable syntax that lets you get the values directly, which is more efficient.

for i in primes:
    if attempt % i == 0:

But rather than using a for loop at all you can use all. It employs short circuiting and will immediately stop iterating over the loop when it finds any value that has an invalid factor. This is faster than breaking when a prime is found, as primes are much rarer than non primes especially when you get into the high values.

def primes(n):
    primes = [2]
    attempt = 3
    while len(primes) < n:
        if all(attempt % prime != 0 for prime in primes):
            primes.append(attempt)
        attempt += 2
    return primes[-1]

Note, you also forgot to increment attempt when a prime was found. That means that every time you found a prime, it then had to be checked yet again in a very costly way since only the last element in the list would invalidate it.

\$\endgroup\$
4
  • \$\begingroup\$ Thanks! These were the kind of tips I was looking for (although I was happy to see more mathematically efficient answers too) The printing was just to help myself troubleshoot and I posted it here by accident. Re: all vs for and break, what's the difference exactly? I thought my for loop was designed to try dividing "attempt" by the prime numbers (in the list) and break if at any point attempt % primes[i] == 0. Is all faster because of the way it's coded? \$\endgroup\$ Sep 1, 2015 at 19:44
  • 3
    \$\begingroup\$ @NicholasHassan my understanding is that a built-in function is almost always better than a for-loop in Python because you move the work into a faster language and out of Python. \$\endgroup\$
    – sunny
    Sep 1, 2015 at 20:51
  • 1
    \$\begingroup\$ @NicholasHassan Sorry about being late with this, but @sunny is correct. This answer confirms that functions like sum, any and all actually run in C (which is faster) instead of Python. \$\endgroup\$ Sep 11, 2015 at 9:15
  • \$\begingroup\$ But if you want to learn programming then try to avoid all these tricks. You need to properly test edge cases and in that case understanding nativefor loops is must. \$\endgroup\$
    – CodeYogi
    Sep 20, 2015 at 16:34
13
\$\begingroup\$

Sometimes, when your code is very slow, you just need a new algorithm. SuperBiasedMan's solution makes many good improvements on your code (taking it from 12.4s on my box -- after removing the unnecessary prints -- to just 5.4s). But we can do better. The issue is, we're still checking every odd number in a row and basically learning nothing from all our previous work. The Sieve of Eratosthenes is a very fast algorithm for computing a large number of primes. The idea is simple: we start with all numbers initially as prime candidates, and we iterate through them. If we find a number still marked prime, we mark all of its multiples as not prime. Repeat until done.

The only issue is that we need to store things in memory. For 10,000 primes though, that's not so bad. There's a well known estimate for the number of primes: p_n ~ n log(n). It's a very good estimate such that the ratio is pretty close to 1, so we can start with twice as much memory for good measure:

def primes_sieve(n):
    p_n = int(2 * n * math.log(n))       # over-estimate p_n
    sieve = [True] * p_n                 # everything is prime to start
    count = 0

Then we start at 2, and start crossing off numbers

    for i in range(2, p_n):
        if sieve[i]:                       # still prime?
            count += 1                     # count it!
            if count == n:                 # done!
                return i
            for j in range(2*i, p_n, i):   # cross off all multiples of i
                sieve[j] = False

And that's it. This takes 0.1 seconds. The reasoning is that we're taking advantage of past work. Once we know that, for instance, 11 is prime - we don't have to do any more work for 121 or 407 or whatever. They're already crossed off!

The time difference grows as we go up in count. For the 100,001st prime, using a sieve gives you the answer in 0.8s whereas a naive loop takes just under 9 minutes (8:53.5).

\$\endgroup\$
2
\$\begingroup\$

Integer division (and that includes the modulo % instruction) is a pretty expensive operation, several times slower than any other arithmetic operation, and you are having to do many of those. It would be nice if you could you a more sieve-like approach, where modulo operations are replaced by stepped iteration.

Of course the issue with a sieve is that you do not know how far out you need to go to find the 10001st prime. So what we need is a sieve-like procedure that allows us to extend an existing prime list. If you are familiar with the sieve of Erathostenes, the following code should not be too hard to understand:

def extend_primes(n, prime_list):
    if not prime_list:
        prime_list.append(2)
    first_in_sieve = prime_list[-1] + 1
    sieve = [True] * (n - first_in_sieve + 1)

    # Sieve all multiples of the known primes
    for prime in prime_list:
        start = prime * prime
        if start < first_in_sieve:
            # Rounded up integer division * prime
            start = ((first_in_sieve - 1) // prime + 1) * prime
        if start > n:
            break
        start -= first_in_sieve
        for idx in range(start, len(sieve), prime):
            print idx + first_in_sieve
            sieve[idx] = False

    # Sieve all multiples of the primes in the sieve
    for prime, is_prime in enumerate(sieve):
        if not is_prime:
            continue
        prime += first_in_sieve
        start = prime * prime
        if start > n:
            break
        start -= first_in_sieve
        for idx in range(start, len(sieve), prime):
            print idx + first_in_sieve
            sieve[idx] = False

    # Extend prime_lsit with new primes
    prime_list.extend(p + first_in_sieve
                      for p, is_p in enumerate(sieve) if is_p)

Now that you have a way of extending a prime list, you just need to extend it until it has sufficient items in it. A not too sophisticated way of going about it could be:

def find_nth_prime(n):
    prime_list = [2]
    limit = n
    while len(prime_list) < n:
        extend_primes(limit, prime_list)
        limit *= 2
    return prime_list[n - 1]

This produces the correct result in a fraction of a second.

Alternatively, you could use the fact that the prime counting function is bounded from above by the logarithmic integral, and do normal sieving up to that value. But that would take some of the algorithmic fun away from this problem.

\$\endgroup\$
2
\$\begingroup\$

One of the reasons your script is slow is that you're building an array:

primes.append(attempt)

Over time, the array will become quite large and the performance degrades. Since the answer you're looking for is a singular value, why not optimize out the need to have an array:

def is_prime(n):
    if n < 2:
        return False
    i = 2
    while (i * i <= n):
        if n % i == 0:
            return False
        i = i + 1
    return True

def n_prime(n):
    i = 2
    while n > 0:
        if is_prime(i):
            n = n - 1
            if n == 0:
                return i
        i = i + 1
    return -1

    print n_prime(10001)

In your routine, you implement is_prime(n) by checking if it's divisible by primes you've found before it. Whereas, I've reduce the complexity by checking to see n is divisible by the integers in 2..sqrt(n). i.e. I'm lazily checking with non-primes as well, but, I've optimize the search by only checking up to sqrt(n).

Then we just iterate call is_prime(i) in a loop until we've encountered n-primes.

For your specific problem, the answer is 104743.

\$\endgroup\$
1
  • \$\begingroup\$ As you were talking about list creation, I thought you were about to talk about iterators and all the good things they bring you. Unfortunately, you didn't so I thought you'd be interested to see how your code can be improved by using iterators. Here you are : gist.github.com/SylvainDe/a29d616684b45f28bd3c . I've kept intermediate versions so that you can see how things are changed. Ultimately, you have is_prime (3 lines, could be 2), nth (2 lines), yield_primes (3 lines) and you can compose them easily. \$\endgroup\$
    – SylvainD
    Sep 2, 2015 at 15:45
1
\$\begingroup\$

You have an interesting optimization in your code: you use the fact that the first prime number is 2 to skip all tests of this value, and increment each test by 2.

Call this fact out in a comment!

I agree with SuperBiasedMan that it is potentially confusing, and should be called out. One place it is confusing is in the while loop comparison, where you have to write < (n - 1). It's usually easier to read comparisons when the actual number is in the comparison, whether that means changing from a less than to a less than or equal, or changing the initialization as in this example. Add the value to your list by initializing it with primes = [2] or, if you want to be verbose:

primes = []
# Initialize the algorithm with the first prime
primes.append[2]

# All other primes are not divisible by previous entries in 'primes' collection
...algorithm...

But, if you do this, every future loop starts out by testing 2, which is a performance hit that you worked around by incrementing by 2. Either start your loop on the second iteration, or don't add it to the list.

Especially in mathematics problems like this, there is always a trade-off between speed and readability. Isolate it from the users of your code, and only optimize when actually necessary, but make it a conscious decision. Usually, business logic is whatever's clearer, and back-end algorithms like this is whatever's fastest.

There are many prime generation algorithms you can use (which is another code review bit of advice: use existing libraries and research!) or you can optimize what you have. For starters, you don't need to check the whole list - just until the factor being tested is greater than or equal to the square root of your current potential prime candidate. 13 will not be a factor of 14, you only need to check up to 3. But is it faster? Square root is expensive on some hardware. Maybe use a square root approxomation. You'll need benchmarks. And now why is there a square root in your prime verification? It will need a comment!

\$\endgroup\$
1
  • \$\begingroup\$ You don't need to comment everything. I would have to say that the square-root check is pretty much common knowledge when doing prime checks, and a comment is more likely to be important if you decide to not use it for some reason, because the next guy along will likely put it in to try to speed it up. \$\endgroup\$
    – user34073
    Sep 1, 2015 at 20:26

Not the answer you're looking for? Browse other questions tagged or ask your own question.