Sieve of Pritchard: Difference between revisions
Content added Content deleted
(→Julia: Started by noticing that the max() should be a min(), then noticed there were some other places that could be made more efficient.) |
m (blue style formatting) |
||
| Line 93: | Line 93: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
{{trans|Raku}} |
|||
Added add/remove statistics. "Removed" figure is a combination of composites and primes under sqrt of limit. |
Added add/remove statistics. "Removed" figure is a combination of composites and primes under sqrt of limit. |
||
Running on Julia 1.0 |
|||
<syntaxhighlight lang="julia">""" Rosetta Code task rosettacode.org/wiki/Sieve_of_Pritchard """ |
<syntaxhighlight lang="julia">""" Rosetta Code task rosettacode.org/wiki/Sieve_of_Pritchard """ |
||
""" Pritchard sieve of primes up to limit |
""" Pritchard sieve of primes up to limit. Uses type of `limit` arg for type of primes """ |
||
| ⚫ | |||
""" using Julia 1.0 (on Tio.run) """ |
|||
| ⚫ | |||
members = Set(one(T)) |
members = Set(one(T)) |
||
steplength = 1 # wheel size |
steplength = 1 # wheel size |
||
| Line 113: | Line 107: | ||
rtlim = T(floor(sqrt(limit))) # this allows the main loop to go |
rtlim = T(floor(sqrt(limit))) # this allows the main loop to go |
||
while prime <= rtlim # one extra time, eliminating the follow-up for |
while prime <= rtlim # one extra time, eliminating the follow-up for |
||
# the last partial wheel (if present) |
|||
if steplength < limit |
if steplength < limit |
||
for w in members |
for w in members |
||
| Line 127: | Line 121: | ||
np = 5 |
np = 5 |
||
for w in sort!(collect(members)) |
for w in sort!(collect(members)) |
||
np == 5 && w > prime && (np = w) |
|||
n = prime * w |
n = prime * w |
||
n > nlimit && break |
|||
rc += 1 |
rc += 1 |
||
delete!(members, n) |
delete!(members, n) |
||
end |
end |
||
np < prime && break |
|||
push!(primes, prime) |
push!(primes, prime) |
||
# this works, but doubles the runtime for limit = 1000000 |
|||
# prime = prime == 2 ? 3 : sort!(collect(members))[2] |
|||
# this is faster |
|||
prime = prime == 2 ? 3 : np |
prime = prime == 2 ? 3 : np |
||
| ⚫ | |||
nlimit = min(steplength * prime, limit) # advance wheel limit |
nlimit = min(steplength * prime, limit) # advance wheel limit |
||
end |
end |
||
delete!(members, 1) |
delete!(members, 1) |
||
verbose && println( |
|||
"up to $limit, added $ac, removed $rc, prime count ", |
|||
length(primes) + length(members), |
|||
| ⚫ | |||
return sort!(append!(primes, members)) |
return sort!(append!(primes, members)) |
||
end |
end |
||