Algorithm for calculating primes in an interval not working

user_19130613 0
Viewed 60

I am trying to come up with an algorithm that can find all primes from a starting to an ending number, without starting at 2 and using the Sieve of Eratosthenes to calculate all primes to the ending number and cutting out the interval I want. And not bruteforcing every number in the interval.

I modified an existing notation of the Sieve of Eratosthenes in python. This is what I got so far:

def m(n: int, l: list):
    for i, v in enumerate(l):
        if v % n == 0 and v != n and v != False:
            break
    for v in range(i, len(l), n):
        l[v] = False
    return l

This function can set all common multiplies of a number n in the array l to false, using the same principle as the Sieve of Eratosthenes when marking non-prime numbers. This is how the function is getting called:

l = list(range(10, 20))
for i in range(2, 20):
    m(i, l)
print(l)

In this configuration, the program calculates all primes from 10 to (excluded) 20.

The output looks like this:

[False, 11, False, 13, False, False, False, 17, False, False]

But it should look like this:

[False, 11, False, 13, False, False, False, 17, False, 19]

It seems like the last prime number of the array is getting ignored. When I tried to calculate from 10 to (excluded) 21 it detected 19 as a prime number.

What did I do wrong?

sieve-of-eratosthenes primes python
1 Answers

For your specific use case, 19 was getting overwritten by False. I've added a little fallback / sanity check before the second loop starts. You can see what's happening via my print logs:

def m(n: int, l: list):
    # set i to its max value
    broke_out = False
    for i, v in enumerate(l):
        if v % n == 0 and v != n and v != False:
            print(f"breaking on index :{i}")
            broke_out = True
            break
    # SANITY CHECK: if we never broke out of the above loop and we're on the last index, we're done.
    if not broke_out and i == len(l)-1:
        return l
    # now use i as the starting point in this loop
    for x in range(i, len(l), n):
        # if not isinstance(x, int):
        print(f"about to overwrite l[x] which is: {l[x]} where x is: {x}")
        # if l[x] % n == 0:
        l[x] = False
    print(f"State of l before returning : {l}")
    return l

l = list(range(10, 20))

for i in range(2, 20):
    m(i, l)

print(l)

Full output:

breaking on index :0
about to overwrite l[x] which is: 10 where x is: 0
about to overwrite l[x] which is: 12 where x is: 2
about to overwrite l[x] which is: 14 where x is: 4
about to overwrite l[x] which is: 16 where x is: 6
about to overwrite l[x] which is: 18 where x is: 8
State of l before returning : [False, 11, False, 13, False, 15, False, 17, False, 19]
breaking on index :5
about to overwrite l[x] which is: 15 where x is: 5
about to overwrite l[x] which is: False where x is: 8
State of l before returning : [False, 11, False, 13, False, False, False, 17, False, 19]
[False, 11, False, 13, False, False, False, 17, False, 19]
[Finished in 0.1s]
user_42252290
Related