Method 1 (Sieve of Eratosthenes) is definitely the faster method to use.
Starting point on my computer, summing primes less than 100,000 takes 39.916 seconds.
List to Set
The problem is basically this line:
primes_in_range = [2]
This creates a list
, to which you add all odd numbers above 1, and then repeatedly search for existence of a number within (d in primes_in_range
), then for all multiples of that number, search for the multiple (j in primes_in_range
), and then search for it a second time in the process of removing it (primes_in_range.remove(j)
). Searching a list
is an \$O(n)\$ operation. When you do it approximately once for every number in the list, your algorithm devolves to \$O(n^2)\$.
On top of this, you’re computingmath.sqrt(n)
many, many times - a relatively expensive operation - yet the value does not change. You only need to compute it once.
The second item you can solve by computing the \$\sqrt n\$ once, and store it in a local variable.
For the first issue, there are a few possibilities. One, you could use a set
, instead of a list
. A set
has approximately \$O(1)\$ lookup time, which is much faster than \$O(n)\$.
primes_in_range = { 2 }
Since sets are not ordered, you don’t "append()
" items to it, you "add
" them instead.
Time has now dropped to 0.020511 seconds
Since the time has dropped to under a second, let's increase to primes less than 10,000,000 for better time measurements.
Time for summing primes less than 10,000,000: 3.519 seconds
Search to Remove
When removing, you are checking for the existence of the item in primes_in_range
before removing it, since removing it when it is not present will raise an exception. The set
class has a discard
method, which will only remove an item if present. No need to check for it to be present ahead of time.
Time for summing primes less than 10,000,000: 3.453 seconds
Removing Multiples
When you find a prime, d
, you cross off multiples of that prime, starting at 2*d
, and going 3*d
, 4*d
, 5*d
, and so on. But when you determined 3
was a prime number, you crossed off all multiples of 3
, so crossing off 3*d
is a waste of time, for d > 3
. Similarly, crossing off multiples of the prime 5
means crossing off 5*d
for d > 5
is also a waste of time. The first multiple of d
that hasn't been crossed off will be d*d
, so you can remove starting at that point:
for j in range(d * d, n + 1, d):
primes_in_range.discard(j)
Time for summing primes less than 10,000,000: 3.305 seconds
Similarly, since you are only considering odd prime candidates in your sieve, you don't need to cross off any even multiples. Starting at d*d
, the next multiple you need to remove would be (d+2)*d
, not (d+1)*d
. Your step size can be 2*d
.
for j in range(d * d, n + 1, 2 * d):
primes_in_range.discard(j)
Time for summing primes less than 10,000,000: 2.105 seconds
Loop Like a Native
Python has its own looping, which includes incrementing loop indexes. This native Python looping is usually faster than writing loops with their own index manipulation:
primes_in_range = {2}
primes_in_range.update(x for x in range(3, n+1, 2))
for d in range(3, math.isqrt(n) + 1, 2):
if d in primes_in_range:
primes_in_range.difference_update(j for j in range(d * d, n + 1, 2*d))
Here, constructing the set is done with a generator expression in primes_in_range.update(...)
, and removing prime multiples is done with a generator expression in primes_in_range.difference_update(...)
which adds and removes entire swathes of items in a single operation:
Time for summing primes less than 10,000,000: 2.049 seconds
Direct Indexing
However, a set
is still an expensive memory structure to maintain. It requires hashing the values which are being added, creating bins to store the values in, rebinning as the set size changes, and so on. An array of flags is much more efficient, time-wise:
primes_in_range = [False] * n
primes_in_range[2] = True
for x in range(3, n, 2):
primes_in_range[x] = True
for d in range(3, math.isqrt(n) + 1, 2):
if primes_in_range[d]:
for j in range(d * d, n + 1, 2 * d):
primes_in_range[j] = False
total = sum(idx for idx, flag in enumerate(primes_in_range) if flag)
The first line, above, allocates an array of n
items, each containing the flag value False
. Then, indexing into the array is an \$O(1)\$ operation. Set the flag to True
for all odd numbers above 3, and then proceed to set the appropriate flags to False
based on the Sieve of Eratosthenes algorithm.
Time for summing primes less than 10,000,000: 1.398 seconds
Bit Array
That last approach is a little inefficient when it comes to memory. It requires a list of n
28-byte items to store one True
/False
flag. These flags could be packed 8 to a byte, resulting in a 99.5% reduction in required memory! The bitarray
package provides such an array of flags.
from math import isqrt
from bitarray import bitarray
def sum_of_primes_below(n):
primes_in_range = bitarray(n)
primes_in_range.setall(False)
primes_in_range[2] = True # 2 is a prime
primes_in_range[3::2] = True # Odd numbers starting at 3 are prime candidates
for d in range(3, isqrt(n) + 1, 2):
if primes_in_range[d]:
primes_in_range[d*d::2*d] = False # Reset multiples of prime candidate
return sum(idx for idx, flag in enumerate(primes_in_range) if flag)
Time for summing primes less than 10,000,000: 0.455 seconds