Why is my sieve of sundaram so inefficient

I have been playing around with prime sieves and their performance. I’ve turned to the Sundaram sieve. My implementation is:

import time
from pympler import asizeof

start = time.perf_counter()
limit = 10000
upper = int(limit/2)
numbers = [i for i in range(upper)]

for j in range(1,int(upper/2)):
    i = 1
    while i <= j:
        n = i + j + (2*i*j)
        if n in numbers and n < upper:
            numbers[numbers.index(n)] = 0
        i += 1

primes = [2, 3]
for number in numbers:
    if number != 0:
        primes.append(number*2 + 1)

stop = time.perf_counter()
print(primes)
print(f'Time = {stop - start} sec')
print(f'List of numbers: {asizeof.asizeof(numbers)}')
print(f'List of primes: {asizeof.asizeof(primes)}') 

The performance results are:

• primes below 100: 0.0002 sec
• primes below 1000: 0.0772 sec
• primes below 10000: 97.71 sec
• primes below 100000: > 30 mins (I terminated the execution)

I don’t think the algorithm is inefficient and my implementation of other algorithms are much quicker than this one so it must be my code. What part of my code is causing the run time to blow out this badly?

>Solution :

You don’t need to perform n in numbers. No need to call index to find the index, because the index is … n. Just check that n is in range, and just set numbers[n] to zero, even when it was already zero.

Besides that there are some things to improve:

• Don’t add 3 explicitly, as it is added by the final loop
• Don’t use float division when you need integer division (//)
• Don’t start with i at 1 at each iteration. You can start at j and deal with the range where i >= j (This is how Wikipedia has it)
• When n is out of range, don’t continue the loop. This becomes the exit condition of your loop.

Here is the part that needs correction:

upper = limit // 2  # use integer division
numbers = list(range(upper))

for j in range(1, upper//2):
    i = j  # Deal with the range from j onwards (until n exceeds)
    while True:
        n = i + j + 2 * i * j
        # No need to check membership in numbers
        if n >= upper:  # This is an exit condition. No need to continue
            break
        numbers[n] = 0
        i += 1
# Don't add 3 explicitly, as it will be added by the loop
# Use comprehension:
primes = [2] + [number*2 + 1 for number in numbers if number]