So yet another Sieve of Eratosthenes in Python 3.
The function returns a list of all primes smaller but not equal
The motivation is, as a practice, a simple implementation of the algorithm that is faithful, short, readable and transparent, while still getting a reasonable performance.
def primes(max_n): """Return a list of primes smaller than max_n.""" sieve = [True] * max_n # p contains the largest prime yet found. p = 2 # Only for p < sqrt(max_n) we check, # i.e. p ** 2 < max_n, to avoid float issues. while p ** 2 < max_n: # Cross-out all true multiples of p: for z in range(2 * p, max_n, p): sieve[z] = False # Find the next prime: for z in range(p + 1, max_n): if sieve[z]: p = z break # 0 and 1 are not returned: return [z for z in range(2, max_n) if sieve[z]]
IMHO it would be preferable to avoid
p ** 2 < max_n and instead use
p < max_n ** 0.5. Can we do this? It surprisingly seems to work as long as
max_n ** 0.5 fits into the float mantissa, even if
for-loop doesn’t look very nice with the
break but I don’t have any idea how to do it otherwise…
Do you have any suggestions?
Are there still any simplifications possible? Or non-hackish ways to increase performance?