Sieve of Pritchard: Difference between revisions
include rephrasing of Mike Day's performance optimization
(include rephrasing of Mike Day's performance optimization) |
|||
Line 163:
=={{header|J}}==
Implementation
<syntaxhighlight lang="j">pritchard=: {{N=. y
spokes=. $.6$4{.1▼
while. y > #spokes do.▼
p=. 0
primes=. primes, p=. 2+(}.spokes) i.1 NB. find next prime
rim=. #spokes NB. "length" of "circumference" of wheel
spokes=. (
NB. remove multiples of this next prime:
spokes=.
end.
N (>:#]) primes,1+}.,I.spokes
while. y > p*p do.▼
primes=. primes, p=. 2+(}.spokes) i.1 NB. find next prime▼
end.▼
▲ primes,1+}.,I.spokes
}}</syntaxhighlight>
Line 182:
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</syntaxhighlight>
However, this approach exhibits performance problems when N is large.
A faster approach recognizes when the wheel is large enough and treats all subsequent "next primes" specially:
<syntaxhighlight lang="j">pr =: {{N=.y
root=. <.%:N NB. performance optimzation
circumference=. 1
spokes=. ,1
primes=. ''
circumference=. N <. p * L NB. next larger wheel:
spokes=. circumference (>:#]), spokes +/~ L * i.circumference >.@% L
NB. remove multiples of this next prime:
spokes=. spokes -. p * spokes ( [{.~ >:@:(I.-(-.@e.)~))circumference<.@%p
▲ end.
NB. set up for optimized version of above code
comb=. root (>#]) }. spokes NB. candidate next primes to consider
discardp=. discard=. '' NB. what we'll be eliminating
for_p. comb do.
if. p e. comb =. comb (-. }.) discardp do.
NB. remove multiples of this next prime:
discardp=. p * spokes ( [{.~ >:@:(I.-(-.@e.)~))circumference<.@%p
discard =. discard, discardp
end.
end.
primes,comb,}.spokes-.discard
}}</lang>
Here, <code>pr 150</code> gives the same result as <code>pritchard 150</code> but <code>pr 1e7</code> takes well under a second.
=={{header|Julia}}==
| |||