pythonprimessieve-algorithm

Sieve of eratosthenes python script outputs non prime numbers


I am making a python (3.10) program that counts all prime numbers and adds them to a list (already containing 2) and somehow This program outputs 16 and 50 in the list (both divisible by 2 so not prime numbers) as well as some other less notable non primes (27 , 35, 65)

i = 3 
primes= [2] 
while len(primes)< 25:
    for x in range(len(primes)):
        if i%primes[x] == 0 : 
            i+= 1
            continue
    primes.append(i)
    i+=1

print(primes)

running the program outputs:

[2, 3, 5, 7, 11, 13, 16, 17, 19, 23, 27, 29, 31, 35, 37, 41, 43, 47, 50, 53, 59, 61, 65, 67, 71]

where it should output:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

I haven't tried a lot of anything else


Solution

  • What you want to do is to break the inner loop, not to continue it; and to update the list in the else clause of the loop:

    i = 3
    primes= [2]
    while len(primes)< 25:
        for x in range(len(primes)):
            if i%primes[x] == 0 :
                break
        else:
            primes.append(i)
        i+=1 # i+=2 would be twice faster, we don't need to check even numbers
    
    print(primes)
    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]