From aef019b04a249cf6c395e663f9e27a4d63cf2ae2 Mon Sep 17 00:00:00 2001 From: "Miss Islington (bot)" <31488909+miss-islington@users.noreply.github.com> Date: Tue, 12 Sep 2023 07:00:33 -0700 Subject: [3.12] Improve the sieve() recipe in the itertools docs (gh-109199) (#109203) Improve the sieve() recipe in the itertools docs (gh-109199) Lazier sieve (cherry picked from commit d3ed9921cdd8ac291fbfe3adf42f7730d3a14dbc) Co-authored-by: Raymond Hettinger --- Doc/library/itertools.rst | 11 +++++++---- 1 file changed, 7 insertions(+), 4 deletions(-) diff --git a/Doc/library/itertools.rst b/Doc/library/itertools.rst index 72c6851..5c4d172 100644 --- a/Doc/library/itertools.rst +++ b/Doc/library/itertools.rst @@ -1030,13 +1030,16 @@ The following recipes have a more mathematical flavor: def sieve(n): "Primes less than n." # sieve(30) --> 2 3 5 7 11 13 17 19 23 29 + if n > 2: + yield 2 + start = 3 data = bytearray((0, 1)) * (n // 2) - data[:3] = 0, 0, 0 limit = math.isqrt(n) + 1 - for p in compress(range(limit), data): + for p in iter_index(data, 1, start, limit): + yield from iter_index(data, 1, start, p*p) data[p*p : n : p+p] = bytes(len(range(p*p, n, p+p))) - data[2] = 1 - return iter_index(data, 1) if n > 2 else iter([]) + start = p*p + yield from iter_index(data, 1, start) def factor(n): "Prime factors of n." -- cgit v0.12