[FIXED] I tried to find all primes up to a value n with sieve_of_eratosthenes algorithm

Issue

I'm very new and I'm not sure if i'm just stupid but I thought it try and just ask. I created a list with all numbers from 2 up to n. Then it should start with the 2, cross out all the numbers that are divisible by to form the list. Then 3 do the same. 4 should be crossed off. 5 and so on. but 3 gets crossed off and the output list is all wrong and I can't figure out why.

here's my code

n=10
list = []
primes_up_to_n = []
p = 0

for z in range(n):
    if z > 0:
        list.append(z+1)

for i in list:
    primes_up_to_n.append(i)
    for t in list:
        if t % i == 0:
            list.remove(t)
print(primes_up_to_n)

Solution

Don't remove items from lists as you are iterating over them, it will cause the iteration to skip over items you don't want it to.

Instead, let's have a list where index 0 represents the number 2 and we just replace non-prime values with None. We can also use the step of the range function to only visit candidates we know are divisible by the prime.

prime_candidates = list(range(2, n+1))
for index, prime in enumerate(prime_candidates):
    if prime is None:
        continue  # Ignore non-primes in our list
    for candidate_index in range(index+prime, len(prime_candidates), prime):
        # range(index+prime, len(prime_candidates), prime)
        # For each prime p, we start at 2p and mark it non-prime
        # We then do the same for Np for each N until we pass the size of our list
        prime_candidates[candidate_index] = None

print([prime for prime in prime_candidates if prime])

Answered By - Patrick Haugh