Sieve of Sundaram is not removing all numbers

Question

I am working on a Python homework that asks me to code the Sieve of Sundaram:

*- start with a list of numbers from 1 to n;

• for every pair of integers i and j where 1<= i <= j and i + j + 2ij <= n, remove i + j + 2ij from - the list above;
• finally, for each remaining number k in the list, 2k+1 is a prime number.*

This is my code:

n = int(input())
num_lst = list(range(1, n + 1))

for i in num_lst:
    for j in num_lst:
        if (1 <= i <= j) and (i + j + (2 * i * j)) <= n:
            num_lst.remove((i + j + (2 * i * j)))
    
print(num_lst)

for idx, k in enumerate(num_lst):
    num_lst[idx] = 2 * k + 1

print(num_lst)

I see many solutions that uses list comprehensions, but at this point of the class, we have not covered it yet.

When input is 50, I'm getting prime numbers up until 101; but I'm also getting some that are not primes (27, 45, 63, 99). What did I do wrong?

Answer 1

Tried this:

n = int(input())
num_lst = list(range(1, n + 1))
to_remove = set()

for i in num_lst:
    for j in num_lst:
        if 1 <= i <= j and i + j + 2 * i * j <= n:
            to_remove.add(i + j + 2 * i * j)

# Remove elements from num_lst after the nested loops
for num in to_remove:
    if num in num_lst:
        num_lst.remove(num)

print(num_lst)

for idx, k in enumerate(num_lst):
    num_lst[idx] = 2 * k + 1

print(num_lst)

OUTPUT:

50
[1, 2, 3, 5, 6, 8, 9, 11, 14, 15, 18, 20, 21, 23, 26, 29, 30, 33, 35, 36, 39, 41, 44, 48, 50]
[3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101]