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?
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]