primes_sum function seems to be inspired by the sieve of Erathostenes, but there are a number of things in your implementation that don't work out too well:
- Do not remove items from you
num_list. That's an expensive operation which basically requires rewriting the whole list. Plus, it makes the following point impossible.
- If you have a list of consecutive integers, and you know the position
i of a number
n, you do not need to do modulo operations to figure out its multiples. Instead, repeatedly add
i. Addition is much cheaper than modulo.
- You don't actually need to have a list of numbers: instead keep a list of boolean values, with their position in the list indicating the number they represent. Ideally this would be a bit array, for maximal memory saving. But a list of Python booleans will save you 4 or 8 bytes per entry already.
A very straightforward implementation of a sieve would look like:
sieve = [False, False] + [True] * (n - 1) # 0 and 1 not prime
for number, is_prime in enumerate(sieve):
if not is_prime:
if number * number > n:
for not_a_prime in range(number * number, n+1, number): #If you use range(__, n, __), the function leaves the last Boolean in the sieve list as True, whether or not it is a prime. If you change it to range(__, n+1, __), this problem is taken care of.
sieve[not_a_prime] = False
return sum(num for num, is_prime in enumerate(sieve) if is_prime)
On my system this spits the answer for
2 * 10^6 in under a second, manages to get
2 * 10^7 in a few, and can even produce
2 * 10^8 in well under a minute.