I'm practicing writing code less by brute force. I'd like feedback for writing a prime sieve more Pythonic, simpler, or more creatively perhaps.
def prime_sieve(limit):
numbers = dict()
limit = int(limit)
for n in range(2, limit + 1):
numbers[n] = ()
primes = numbers.copy()
for n in numbers:
m = n
while m <= limit:
m = m + n
primes.pop(m, 0)
return primes
Your implementation of the sieve, using a dictionary, throws away many of the benefits of the approach; dictionaries are unordered. Even a naive list-based implementation ends up processing fewer than half as many numbers (146 vs. 382 with a limit of 100):
def sieve(limit):
nums = range(limit+1)
nums[1] = 0
for n in nums:
if n:
for x in range(2*n, limit+1, n):
nums[x] = 0 # counting this vs. pop
return set(filter(None, primes))
Your approach processes multiples of numbers that will subsequently turn out to be non-prime themselves, e.g. you might pop all multiples of 9, then go back over them when you later process 3.
Note that I have used a set, which is effectively a dictionary with no values, rather than have some dummy value.
Also, there was no need to copy the whole dictionary; for n in numbers.keys() would have worked fine.
There are numerous other implementations, in Python and other languages, on this site and elsewhere; I suggest you look at a few to see what other alterations could be made.
