Project Euler 10 - Why is the first Python code so much faster than the second?

Question

10th problem in Project Euler:

The sum of primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all primes below two millions.

I found this snippet:

sieve = [True] * 2000000 # Sieve is faster for 2M primes def mark(sieve, x): for i in xrange(x+x, len(sieve), x): sieve[i] = False for x in xrange(2, int(len(sieve) ** 0.5) + 1): if sieve[x]: mark(sieve, x) print sum(i for i in xrange(2, len(sieve)) if sieve[i]) 

published here which work for 3 seconds.

I wrote this code:

 def isprime(n): for x in xrange(3, int(n**0.5)+1): if n % x == 0: return False return True sum=0; for i in xrange(1,int(2e6),2): if isprime(i): sum += i 

I do not understand why my code (second) is much slower?

Answer 1

Your algorithm checks each number separately from 2 to N (where N = 2,000,000) for primitiveness.

Snippet-1 uses the Eratosthenes sieve algorithm, discovered about 2,200 years ago. It does not check every number, but:

• Makes a "sieve" of all numbers from 2 to 2,000,000.
• Finds the first number (2), marks it as prime, and then removes all its multiples from the sieve.
• Then it finds the next reconstructed number (3), marks it as prime and removes all its multiples from the sieve.
• Then it finds the next reconstructed number (5), marks it as prime, and removes all its multiples from the sieve.
• ...
• Until he finds the value of 1409 and removes all its multiples from the sieve.
• Then all primes up to 1414 ~ = sqrt (2,000,000) were found and stopped
• Numbers from 1415 to 2,000,000 do not need to be checked. Everyone who has not yet been deleted is also simple.

Thus, the algorithm produces all primes up to N.

Note that he does not make any separation, only additions (not even multiplications, and not that it matters with such small numbers, but maybe with big ones). The time complexity is O(n loglogn) , while your algorithm has something around O(n^(3/2)) (or O(n^(3/2) / logn) , as @Daniel Fischer commented) , assuming divisions are the same as multiplications.

From the Wikipedia article (link above):

The complexity of time in the model of a random access machine is O (n log log n) operations, a direct consequence of the fact that the main harmonic series asymptotically approaches log log n .

(with n = 2e6 in this case)

Answer 2

The first version pre-calculates all the primes in the range and stores them in the sieve array, and finding a solution is a simple matter of adding primes to the array. It can be considered as a form of memoization .

The second version checks each number in the range to see if it is prime, repeating the great work already done by previous calculations.

In conclusion, the first version avoids the re-calculation of values, while the second version performs the same operations again and again.

Answer 3

To easily understand the difference, try to think how many times each number will be used as a potential separator:

In your decision, number 2 will be checked for EVERY number when this number is checked to be simple. Each number that you follow along the path will then be used as a potential separator for each subsequent number.

In the first decision, as soon as you step over the number, you never look back - you always move forward from the place where you reached. By the way, a possible and general optimization is to go on odd numbers only after you have noted 2:

 mark(sieve, 2) for x in xrange(3, int(len(sieve) ** 0.5) + 1, 2): if sieve[x]: mark(sieve, x) 

Thus, you only look at each number of times and clear all its multiplications forward, and do not look at all possible divisors again and again, checking each number with all its predecessors, and the if does not allow you to repeat work on the number that you encountered earlier.

Answer 4

As Oscar's answer indicates, your algorithm repeats a lot of work. To see how much processing will be saved in another algorithm, consider the following modified version of the mark() and isprime() functions, which track how many times the function has been called, and the total number of iterations of the loop:

 calls, count = 0, 0 def mark(sieve, x): global calls, count calls += 1 for i in xrange(x+x, len(sieve), x): count += 1 sieve[i] = False 

After starting the first code with this new function, we can see that mark() is called 223 times, for a total of 4,489,006 (~ 4.5 million) iterations in a for loop.

 calls, count = 0 def isprime(n): global calls, count calls += 1 for x in xrange(3, int(n**0.5)+1): count += 1 if n % x == 0: return False return True 

If we make a similar change for your code, we will see that isprime() is called 1,000,000 (1 million) times with 177,492,735 (~ 177.5 million) iterations of the for loop.

Counting function calls and loop iterations are not always a convincing way to determine why an algorithm runs faster, but usually fewer steps == less time, and obviously your code can use some optimization to reduce the number of steps.