-
-
Save tomviner/ddb9474f96f8d0366f5f39bf53208a16 to your computer and use it in GitHub Desktop.
Python 3 Sieve of Eratosthenes - https://upload.wikimedia.org/wikipedia/commons/b/b9/Sieve_of_Eratosthenes_animation.gif
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
from itertools import count, takewhile | |
from math import sqrt | |
import time | |
try: | |
# Python 2 compat | |
from itertools import ifilter as filter | |
except ImportError: | |
pass | |
try: | |
# Python 2 compat | |
range = xrange | |
except NameError: | |
pass | |
def sieve_brevity_ad_absurdum(limit): | |
candidates = set(range(2, limit + 1)) | |
loops = 0 | |
for n in candidates: | |
loops += 1 | |
sieved = set(filter(lambda x: not x % n, candidates - {n})) | |
# create new candidates object, for loop continues over the original | |
candidates = candidates - sieved | |
return sorted(candidates), loops | |
def sieve_absurder_brevity(limit): | |
candidates = set(range(2, limit + 1)) | |
loops = 0 | |
# make a copy of candidates otherwise changing its size will cause | |
# RuntimeError: Set changed size during iteration | |
for n in set(candidates): | |
loops += 1 | |
candidates &= {n} | set(filter(n.__rmod__, candidates)) | |
return sorted(candidates), loops | |
_loops = 0 | |
def _sieve_itertools(): | |
global _loops | |
candidates = count(2) | |
_loops = 0 | |
while True: | |
_loops += 1 | |
n = next(candidates) | |
yield n | |
# this needs to be wrapped in a function otherwise it fails to retain | |
# the local variable context when later lazily run | |
def filter_out_multiples(it, prime=n): | |
return filter(lambda x: x % prime != 0, it) | |
# compose a stack of iterators that each remove multiples of a prime | |
candidates = filter_out_multiples(candidates, prime=n) | |
def sieve_itertools(limit): | |
return list(takewhile(lambda x: x <= limit, _sieve_itertools())), _loops | |
def genuine_sieve_of_eratosthenes(limit): | |
""" See https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf """ | |
candidates = set(range(2, limit + 1)) | |
loops = 0 | |
for n in candidates: | |
if n > sqrt(limit): | |
continue | |
loops += 1 | |
# real sieve of eratosthenes! | |
sieved = set(range(n * n, limit + 1, n)) | |
# create new candidates object, for loop continues over the original | |
candidates = candidates - sieved | |
return sorted(candidates), loops | |
if __name__ == '__main__': | |
limit = 5000 | |
sieves = ( | |
sieve_brevity_ad_absurdum, | |
sieve_absurder_brevity, | |
sieve_itertools, | |
genuine_sieve_of_eratosthenes, | |
) | |
for sieve in sieves: | |
start = time.time() | |
primes, loops = sieve(limit) | |
end = time.time() | |
print('{:>30} {:4d} loops, {:.4f}s, {} primes: [...{}'.format( | |
sieve.__name__, loops, end - start, len(primes), str(primes)[-50:])) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
""" | |
# python 2 only :-( | |
pip install big_o | |
""" | |
from sieve import ( | |
sieve_brevity_ad_absurdum, | |
sieve_absurder_brevity, | |
sieve_itertools, | |
genuine_sieve_of_eratosthenes, | |
) | |
import big_o | |
sieves = ( | |
sieve_brevity_ad_absurdum, | |
sieve_absurder_brevity, | |
sieve_itertools, | |
genuine_sieve_of_eratosthenes, | |
) | |
for sieve in sieves: | |
best, rest = big_o.big_o(sieve, big_o.datagen.n_, min_n=10, max_n=10000) | |
print '{:>27} {}'.format(sieve.__name__, best) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment