This is not a Sieve of Eratosthenes for a few reasons.
Instead of just throwing a real one at you, lets see how we can deduce a Sieve of Eratosthenes just by improving the current code.
The first thing to note is that we can clean up the recursive function be removing the return
; you're only returning the list they already have.
Secondly, you can remove the else
and remove the last if
by making the first check stricter. That gives:
def filter_multiples(lst, n, counter):
''' A recursive method used to remove multiples of n in a list(lst)
and using a counter to iterate through that list
'''
if len(lst) <= counter:
return
# See if a number in a list is divisble by n and if so, remove it
if lst[counter] % n == 0 and lst[counter] != n:
lst.remove(lst[counter])
filter_multiples(lst, n, counter+1)
You then find that the recursive function is easier as a loop:
def filter_multiples(lst, n, counter):
while counter < len(lst):
# See if a number in a list is divisble by n and if so, remove it
if lst[counter] % n == 0 and lst[counter] != n:
lst.remove(lst[counter])
counter += 1
If this insistence to use an imperative style makes you confused about what the point of recursion is, let me assure you there are uses. Traversing tree data structures is traditionally done recursively. Here's some example of that. It's not, however, good to use recursion for the sake of it unless using a language specifically designed to do so.
This uses remove
repeatedly to filter elements. remove
is O(n)
so the overall time for this is O(n²)
. You know this can't be a Sieve of Eratosthenes because the whole sieve is meant to be O(n log n)
!
One way to improve this is to use a list comprehension:
def filter_multiples(lst, n):
lst[:] = [i for i in lst if i == n or i % n]
which, you might think, is then better just using return
:
def filter_multiples(lst, n):
return [i for i in lst if i == n or i % n]
However, the outer loop
for i in odd_nums:
filter_multiples(odd_nums, i)
would be changed to
for i in odd_nums:
odd_nums = filter_multiples(odd_nums, i)
and this means the for i in odd_nums
would be iterating over the old odd_nums
. Thus, this needs to be in place with how you've made it. However, modifying the number of elements in lists while you're iterating over them is heavily discouraged. This means that maybe we should think of a different technique for filter_multiples
.
One such technique is marking all of the elements to remove and then doing a list comprehension:
for i, val in enumerate(lst):
if not (val == n or val % n):
lst[i] = None
lst[:] = [val for val in lst if val is not None]
The advantage of this is that we can hoist the final comprehension outside of the two loops and just skip None
in the outer loop:
def filter_multiples(lst, n):
for i, val in enumerate(lst):
if val is None:
continue
if not (val == n or val % n):
lst[i] = None
# Cycle through the numbers and use filter_multiples to remove the factors and keep the primes
for val in odd_nums:
if val is not None:
filter_multiples(odd_nums, val)
odd_nums = [val for val in odd_nums if val is not None]
This seems more complicated, true, and it's probably also slower than the comprehension because it's looping over more numbers. However, think about this check:
if not (val == n or val % n):
lst[i] = None
Since we're not compressing lst
, val
will directly map to a given i
(or None
). As such, if we work out that mapping we can avoid the check by just going over all the i
that map to {2n, 3n, 4n, ...}
.
One way of doing that is just making val
map to i
:
sieve = range(100)
sieve[0] = sieve[1] = None
def filter_multiples(lst, n):
for i in range(2*n, len(lst), n):
if lst[i] is None:
continue
lst[i] = None
# Cycle through the numbers and use filter_multiples to remove the factors and keep the primes
for val in sieve:
if val is not None:
filter_multiples(sieve, val)
sieve = [val for val in sieve if val is not None]
print sieve
In fact, the if
is no longer needed inside this loop and we can do:
def filter_multiples(lst, n):
for i in range(2*n, len(lst), n):
lst[i] = None
Then you'd probably want to tidy up the code by putting it in a function:
def mask_indicies(lst, start, step):
for i in range(start, len(lst), step):
lst[i] = None
def primes_below(maximum):
sieve = list(range(maximum))
sieve[0] = sieve[1] = None
for val in sieve:
if val is not None:
mask_indicies(sieve, 2*val, val)
return [val for val in sieve if val is not None]
if __name__ == "__main__":
print(primes_below(100))
That is a Sieve of Eratosthenes. I've added Python 3 compatibility.
Note that I have previously talked about doing similar things really fast, first with a Sieve of Sundaram and then comparing it to a Sieve of Eratosthenes (Eratosthenes won).