From be5de5016637a3a3101c551ca5b162c500a220ce Mon Sep 17 00:00:00 2001
From: "Miss Islington (bot)"
 <31488909+miss-islington@users.noreply.github.com>
Date: Sat, 15 Oct 2022 10:52:45 -0700
Subject: [PATCH] Faster sieve() recipe (GH-98287)

(cherry picked from commit f4370318d67f1f2f686c1c3a4b217ccc461d31e5)

Co-authored-by: Raymond Hettinger <rhettinger@users.noreply.github.com>
---
 Doc/library/itertools.rst | 48 +++++++++++++++++++++++++++++++++++++++
 1 file changed, 48 insertions(+)

diff --git a/Doc/library/itertools.rst b/Doc/library/itertools.rst
index da550e6fa258..2b4d7d535e09 100644
--- a/Doc/library/itertools.rst
+++ b/Doc/library/itertools.rst
@@ -812,6 +812,26 @@ which incur interpreter overhead.
            for k in range(len(roots) + 1)
        ]
 
+   def iter_index(seq, value, start=0):
+       "Return indices where a value occurs in a sequence."
+       # iter_index('AABCADEAF', 'A') --> 0 1 4 7
+       i = start - 1
+       try:
+           while True:
+               yield (i := seq.index(value, i+1))
+       except ValueError:
+           pass
+
+   def sieve(n):
+       "Primes less than n"
+       # sieve(30) --> 2 3 5 7 11 13 17 19 23 29
+       data = bytearray([1]) * n
+       data[:2] = 0, 0
+       limit = math.isqrt(n) + 1
+       for p in compress(range(limit), data):
+           data[p*p : n : p] = bytearray(len(range(p*p, n, p)))
+       return iter_index(data, 1)
+
    def flatten(list_of_lists):
        "Flatten one level of nesting"
        return chain.from_iterable(list_of_lists)
@@ -1156,6 +1176,34 @@ which incur interpreter overhead.
     >>> all(factored(x) == expanded(x) for x in range(-10, 11))
     True
 
+    >>> list(iter_index('AABCADEAF', 'A'))
+    [0, 1, 4, 7]
+    >>> list(iter_index('AABCADEAF', 'B'))
+    [2]
+    >>> list(iter_index('AABCADEAF', 'X'))
+    []
+    >>> list(iter_index('', 'X'))
+    []
+
+    >>> list(sieve(30))
+    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
+    >>> small_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
+    >>> all(list(sieve(n)) == [p for p in small_primes if p < n] for n in range(101))
+    True
+    >>> len(list(sieve(100)))
+    25
+    >>> len(list(sieve(1_000)))
+    168
+    >>> len(list(sieve(10_000)))
+    1229
+    >>> len(list(sieve(100_000)))
+    9592
+    >>> len(list(sieve(1_000_000)))
+    78498
+    >>> carmichael = {561, 1105, 1729, 2465, 2821, 6601, 8911}  # https://oeis.org/A002997
+    >>> set(sieve(10_000)).isdisjoint(carmichael)
+    True
+
     >>> list(flatten([('a', 'b'), (), ('c', 'd', 'e'), ('f',), ('g', 'h', 'i')]))
     ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i']
 
-- 
2.47.3