Sieve of Pritchard: Difference between revisions
m
→{{header|Python}}
Line 286:
<syntaxhighlight lang="python">
""" Rosetta Code task rosettacode.org/wiki/Sieve_of_Pritchard """
from numpy import ndarray
from math import isqrt
def pritchard(limit):
""" Pritchard sieve of primes up to limit """
members =
members.fill(False)
steplength, prime = 1, 2▼
members[1] = True
▲ steplength, prime, rtlim, nlimit = 1, 2, isqrt(limit), 2
primes = []
while
if steplength < limit:
n = w + steplength
while n <= nlimit:
members
n += steplength
steplength = nlimit
if n > steplength: break # no use trying to remove items that can't even be there▼
for w in range(1, len(members
if np == 5 and w > prime:
if n > nlimit:
members[n] = False # no checking necessary now
if np < prime:
break
primes.append(prime)
prime = 3 if prime == 2 else
newprimes = [i for i in range(2, len(members)) if members[i]]
▲ n = w + steplength
▲ while n <= limit:
▲ members.add(n)
▲ n += steplength
▲ return primes + sorted(members)[1:]
print(pritchard(150))
print('Number of primes up to 1,000,000:', len(pritchard(1000000)))
</syntaxhighlight>{{out}}<pre>[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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149]</pre>▼
</syntaxhighlight>{{out}}
<pre>
▲
Number of primes up to 1,000,000: 78498
</pre>
=={{header|Raku}}==
| |||