Prime decomposition: Difference between revisions
→Python: Using Croft Spiral sieve: make croft() another ~1.5% faster by duplicating only once per entry; remove unused dict inits
(→Python: Using Croft Spiral sieve: make croft() another ~2% faster (all measuring done with Python 3.11.1 and the first million primes)) |
(→Python: Using Croft Spiral sieve: make croft() another ~1.5% faster by duplicating only once per entry; remove unused dict inits) |
||
Line 4,073:
for p in (2, 3, 5):
yield p
roots = {
not_primeroot = tuple(x not in {1,7,11,13,17,19,23,29} for x in range(30))
q = 1
Line 4,079:
# Iterate over prime candidates 7, 11, 13, 17, ...
q += x
# Using dict membership testing instead of pop gives a
# 5-10% speedup over the first three million primes.
if q in roots:
p = roots.pop(q)
while not_primeroot[x % 30] or x in roots:
x +=
roots[x] = p
else:
roots[q * q] = q + q
yield q
primes = croft
| |||