The sieve of Sundaram: Difference between revisions
m
→{{header|AppleScript}}: Optimisation better explained in the comments.
m (→{{header|AppleScript}}: Minor comment edit.) |
m (→{{header|AppleScript}}: Optimisation better explained in the comments.) |
||
Line 99:
end script
-- Build a list of at least as many 'true's as there are notionally initially unmarked
--
set {unmarked, marked} to {true, false}
-- 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
-- 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
Line 116:
-- 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 i to 1
Line 130 ⟶ 134:
if (i ≥ n2) then exit repeat -- Enough primes obtained.
set step to step + 2
repeat with j from (n + 2 + step) to (limit - step) by step * 3
set item j of o's lst to marked
| |||