Sieve of Pritchard: Difference between revisions
Created Nim solution.
m (→{{header|AppleScript}}: Speeded up.) |
(Created Nim solution.) |
||
Line 445:
</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]
up to 1000000, added 186825, removed 108494, prime count 78498
</pre>
=={{header|Nim}}==
{{trans|Python}}
<syntaxhighlight lang="Nim">import std/[algorithm, math, sugar]
proc pritchard(limit: Natural): seq[int] =
## Pritchard sieve of primes up to "limit".
var members = newSeq[bool](limit + 1)
members[1] = true
var
stepLength = 1
prime = 2
rtlim = sqrt(limit.toFloat).int
nlimit = 2
primes: seq[int]
while prime <= rtlim:
if stepLength < limit:
for w in 1..members.high:
if members[w]:
var n = w + stepLength
while n <= nlimit:
members[n] = true
inc n, stepLength
stepLength = nlimit
var np = 5
var mcpy = members
for w in 1..members.high:
if mcpy[w]:
if np == 5 and w > prime:
np = w
let n = prime * w
if n > limit:
break # No use trying to remove items that can't even be there.
members[n] = false # No checking necessary now.
if np < prime:
break
primes.add prime
prime = if prime == 2: 3 else: np
nlimit = min(stepLength * prime, limit) # Advance wheel limit.
let newPrimes = collect:
for i in 2..members.high:
if members[i]: i
result = sorted(primes & newPrimes)
echo pritchard(150)
echo "Number of primes up to 1_000_000: ", pritchard(1_000_000).len
</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]
Number of primes up to 1_000_000: 78498
</pre>
| |||