The sieve of Sundaram: Difference between revisions
Content added Content deleted
m (→{{header|AppleScript}}: Minor comment edit.) |
m (→{{header|AppleScript}}: Optimisation better explained in the comments.) |
||
Line 99: | Line 99: | ||
end script |
end script |
||
-- Build a list of at least as many 'true's as there are notionally initially |
-- Build a list of at least as many 'true's as there are notionally initially unmarked |
||
-- |
-- numbers. The numbers themselves are implied by the 1-based indices. |
||
set {unmarked, marked} to {true, false} |
set {unmarked, marked} to {true, false} |
||
-- The Python and Julia solutions note that the nth prime is approx n * 1.2 * log(n), |
-- The Python and Julia solutions note that the nth prime is approx n * 1.2 * log(n), |
||
-- but the number from which it'll be |
-- but the number from which it'll be generated is about half that. |
||
-- 15 is added too here to ensure headroom when working with lower prime counts. |
-- 15 is added too here to ensure headroom when working with lower prime counts. |
||
set limit to (do shell script "echo '" & n2 & " * 0.6 * l(" & n2 & ") + 15'| bc -l") as integer |
set limit to (do shell script "echo '" & n2 & " * 0.6 * l(" & n2 & ") + 15'| bc -l") as integer |
||
Line 116: | Line 116: | ||
-- Apply the sieve, storing generated primes in consecutive slots from the beginning of the list. |
-- Apply the sieve, storing generated primes in consecutive slots from the beginning of the list. |
||
-- Slots whose index mod 3 is 1 aren't tested, since, except for 1 itself, they're assumed to be |
|||
-- "marked". Since each marking sweep begins at one of these indices, the first index of every |
|||
-- three in the sweep, mod 3, must also be 1, so there's no point in actually marking that slot, |
|||
-- although it'll probably get marked incidentally in sweeps based on other intervals. |
|||
set step to 1 |
set step to 1 |
||
set i to 1 |
set i to 1 |
||
Line 130: | Line 134: | ||
if (i ≥ n2) then exit repeat -- Enough primes obtained. |
if (i ≥ n2) then exit repeat -- Enough primes obtained. |
||
set step to step + 2 |
set step to step + 2 |
||
-- The first of every three markings in each sweep (or the third, |
|||
-- depending on where the count starts) can be omitted, since |
|||
-- it'll be covered by other sweeps or the slot overwritten. |
|||
repeat with j from (n + 2 + step) to (limit - step) by step * 3 |
repeat with j from (n + 2 + step) to (limit - step) by step * 3 |
||
set item j of o's lst to marked |
set item j of o's lst to marked |