Sum of primes under a certain number I have tried two different methods to find the sum of primes under a certain number. However both of these methods end up taking a very long time for large numbers. How can I optimise either of these two methods?

Method 1 (Sieve of Eratosthenes):

import time
import math

primes_in_range = [2]

n = int(input("Enter the range of your sieve"))

start = time.time()

for x in range(3, n+1, 2):
    primes_in_range.append(x)

d = 3

while d &lt;= math.sqrt(n):
    if d in primes_in_range:
        for j in range(2 * d, n + 1, d):
            if j in primes_in_range:
                primes_in_range.remove(j)
    d += 2

print(sum(primes_in_range))
end = time.time()
print(end - start)


Method 2:

import time
import math

def is_prime(n):
  if n&gt;1:
    for i in range (2, int(math.sqrt(n)) + 1):
      if (n % i) == 0:
        return False
    else:
      return True
  else:
    return False

n = int(input("Enter the range of your sieve"))

start = time.time()

total = 2

i = 3

while i &lt; n:
    if is_prime(i):
        total += i
    i += 2

print(total)


end = time.time()
print(end -start)
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 &gt; 3.  Similarly, crossing off multiples of the prime 5 means crossing off 5*d for d &gt; 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