3
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ Attempted? Did you succeed? \$\endgroup\$ – Stephen Rauch Jun 22 at 4:33
  • \$\begingroup\$ yes , i did succeed \$\endgroup\$ – its_vinayak Jun 22 at 4:33
  • \$\begingroup\$ Cool, then I suggest you edit the question and add language that indicates same. \$\endgroup\$ – Stephen Rauch Jun 22 at 4:34
  • \$\begingroup\$ thanks @StephenRauch \$\endgroup\$ – its_vinayak Jun 22 at 4:36
1
\$\begingroup\$

Organization

Your function prime_sum() does three things.

  1. It computes primes up to a limit
  2. It sums up the computed primes
  3. It prints out the sum.

What are the odds the next Euler problem will use prime numbers? You’re going to have to write and re-write your sieve over and over again if you keep embedding it inside other functions. Pull it out into its own function.

Summing up the list of prime numbers you’ve generated should be a different function. Fortunately, Python comes with this function built-in: sum().

Will you always print the sum of primes every time you compute it? Maybe you want to test the return value without printing it? Separate computation from printing.

Reorganized code:

def primes_up_to(n):
    # omitted

def prime_sum(n):
    primes = primes_up_to(n)
    return sum(primes)

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

Bugs

As you code presently reads, you compute primes up to n, using range(n+1) for the loop. The +1 ensures you actually include the value n in the loop.

Then, you sum up all the primes using range(n) ... which means you stop counting just before n. Not a problem if you pass a non-prime number for n, but if you passed in a prime, your code would stop one number too early.

It would be much easier to increase n by 1 at the start, to avoid the need to recompute it all the time, and risk accidentally forgetting a +1.

Memory usage

Lists in Python are wonderful, flexible, and memory hungry. A list of 2 million integers could take 16 million bytes of memory, if each element of the list is an 8 byte pointer. Fortunately, the integers 0 and 1 are interned, so no additional memory is required for the storage of each value, but if arbitrary integers were stored in the list, each integer can take 24 bytes or more, depending on the magnitude of the integer. With 2 million of them, that’s an additional 48 million bytes of memory.

If you know in advance you are going to be working with 2 million numbers, which will only every be zeros or ones, you should use a bytearray().

def bytearray_prime_sum(n):
    n += 1
    sieve = bytearray(n)     # An array of zero flags
    sieve[0] = 1
    sieve[1] = 1
    # ... etc ...

There are a few tricks of speeding up your sieve. Two is the only even prime. You can treat it as a special case, and only test odd numbers, using a loop over range(3, n, 2). Once you’ve done that, when marking off multiples of a prime, you can loop over range(i*i, n, 2*i), since the even multiples don’t need to be considered. Finally, when generating the final list of primes (or summing up the primes if you are generating and summing in one step), you can again skip the even candidates, and only consider the odd candidates using range(3, n, 2). Just remember to include the initial 2 in some fashion.

def bytearray_prime_sum(n):
    n += 1
    total = 2
    flags = bytearray(n)
    for i in range(3, n, 2):
        if not flags[i]:
            total += i
            for j in range(i*i, n, 2*i):
                flags[j] = 1
    return total

Memory usage: Take 2

Since we are only storing 0 and 1 flags, a bytearray actually uses 8 times more memory than is necessary. We could store the flags in individual bits. First, we'll want to install the bitarray module:

pip3 install bitarray

Then, we can reimplement the above using a bitarray instead of a bytearray.

from bitarray import bitarray

def bitarray_prime_sum(n):
    n += 1
    total = 2
    flags = bitarray(n)
    flags.setall(False)
    for i in range(3, n, 2):
        if not flags[i]:
            total += i
            flags[i*i::2*i] = True
    return total

Most notably in this bitarray implementation is the flagging of the multiples of a prime became a single statement: flags[i*i::2*i] = True. This is a slice assignment from a scalar, which is a fun and powerful extra tool the bitarray provides.

Timings

Timing graphs

Unfortunately, the above graph shows Justin's implementation has actually slowed down the code over the OP's, due to a mistake Justin made when profiling his "improvement."

\$\endgroup\$
1
\$\begingroup\$

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 -

enter image description here

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)
>>> 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)
>>> 264 ns ± 2.73 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

Key: ms - milliseconds
     ns - nanoseconds

Hope this helps!

\$\endgroup\$
  • 2
    \$\begingroup\$ I haven't profiled it, but I would be enormously surprised if set was cheaper than list for Eratosthenes. It's cheaper to check membership (i.e. in or similar) but the original code does not use in anywhere. Direct access to a known location in a contiguous array is typically about the fastest data structure access available. \$\endgroup\$ – Josiah Jun 22 at 6:36
  • 2
    \$\begingroup\$ You made a couple of errors. #1) timeit eratothenese(2000000) returns the time it takes to create the generator only. You haven't generated any primes at all. If you time over the time it takes to run the generator to completion, sum up the primes, and print the results, I see your implementation running 58% slower. #2) As for using less space? By the end, the multiples set itself takes 67MB, and the contents of the set takes another 52MB, for a total memory usage of 119MB. The OP's solution, the list takes 17MB, the contents 52 bytes for a total of 17MB. \$\endgroup\$ – AJNeufeld Jun 22 at 16:09
  • \$\begingroup\$ @AJNeufeld - Oh, I'm sorry I didn't specify in the answer - I actually meant the code is shorter that way. I don't even know how to find the memory usage! And how did you time the code, though? I'm so confused, I never manage to time a program correctly. Please help me out. Downvotes are welcome since I cannot delete my answer. \$\endgroup\$ – Justin Jun 22 at 16:29
  • 1
    \$\begingroup\$ Let's continue this in chat... \$\endgroup\$ – AJNeufeld Jun 22 at 16:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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