Sum of primes up to 2 million using the Sieve of Eratosthenes I've solved question 10 on Project Euler using the Sieve of Eratosthenes, what can I do to optimize my code?

def prime_sum(n):
    l=[0 for i in range(n+1)]

    l[0]=1
    l[1]=1
    for i in range(2,int(n**0.5)+1):
        if l[i]==0:
            for j in range(i * i, n+1, i):
                    l[j]=1
    s=0
    for i in range(n):
        if l[i] == 0:
            s+=i
    print(s)

if __name__ == '__main__':
    prime_sum(2000000)
Code readability and style -



I believe that good code should have good style and should be more readable and concise.



According to PEP 8 -


  Never use the characters l (lowercase letter el), O (uppercase
  letter oh), or I (uppercase letter eye) as single character variable
  names.
  
  In some fonts, these characters are indistinguishable from the
  numerals one and zero. When tempted to use l, use L instead.




I ran a PEP 8 checker over your code, and here are the results -


  


This means that your code uses inconsistent whitespaces. Therefore, your code (in terms of readability and style) could be improved like this (along with other recommendations) -

def prime_sum(n):
    my_list = [0 for i in range(n+1)]

    my_list[0] = 1
    my_list[1] = 1

    for i in range(2, int(n**0.5) + 1):
        if my_list[i] == 0:
            for j in range(i*i, n+1, i):
                    my_list[j] = 1
    s = 0
    for i in range(n):
        if my_list[i] == 0:
            s += i
    print(s)

if __name__ == '__main__':
    prime_sum(2000000)




Also, good use of the if __name__ == __'main__': guard. Most people don't even attempt to use it.



Improvements to your code -

Python provides a set type which is quite efficient at performing both of those operations (although it does chew up a bit more RAM than a simple list). Gladly, it's easy to modify your code to use a set instead of a list. Computation with sets is much faster because of the hash tables (What makes sets faster than lists in python?).

Also, we don't need to keep a running total of the sum of the primes. It's better to do that at the end using Python's built-in sum() function, which operates at C speed, so it's much faster than doing the additions one by one at Python speed.

So your code would then look like this -

def eratosthenes(n):
    # Declare a set - an unordered collection of unique elements
    multiples = set()
    for i in range(2, n+1):
        if i not in multiples:
           yield i
           multiples.update(range(i*i, n+1, i))

if __name__ == '__main__':
    # Now sum it up
    prime_sum = sum(eratosthenes(2000000))
    print(prime_sum)


which uses less space too.

If you're wondering what yield is...


  The yield statement suspends function’s execution and sends a value
  back to the caller, but retains enough state to enable function to resume
  where it is left off. When resumed, the function continues execution
  immediately after the last yield run. This allows its code to produce
  a series of values over time, rather them computing them at once and
  sending them back like a list.


Source - https://www.geeksforgeeks.org/use-yield-keyword-instead-return-keyword-python/

And if you are wondering what .update() is...


  The update() adds elements from a set (passed as an argument) to the
  set (calling the update() method).
  
  The syntax of update() is -

A.update(B)



Source - https://www.geeksforgeeks.org/python-set-update/



Now let's time your code -

# %timeit prime_sum(2000000)
&gt;&gt;&gt; 648 ms ± 19.7 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)


which does look pretty slow.



With the improved code, the time to execute greatly decreases -

# %timeit eratosthenes(2000000)
&gt;&gt;&gt; 264 ns ± 2.73 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)




Key: ms - milliseconds
     ns - nanoseconds




Hope this helps!