Faster sieve() recipe (GH-98287)
(cherry picked from commit f4370318d67f1f2f686c1c3a4b217ccc461d31e5)
Co-authored-by: Raymond Hettinger <rhettinger@users.noreply.github.com>
diff --git a/Doc/library/itertools.rst b/Doc/library/itertools.rst
index da550e6..2b4d7d5 100644
--- a/Doc/library/itertools.rst
+++ b/Doc/library/itertools.rst
@@ -812,6 +812,26 @@
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 @@
>>> 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']
