The sieve of Sundaram: Difference between revisions
Content added Content deleted
m (→{{header|AppleScript}}: Optimisation better explained in the comments.) |
m (→{{header|AppleScript}}: Yet another optimisation and attendant comment work.) |
||
Line 86: | Line 86: | ||
=={{header|AppleScript}}== |
=={{header|AppleScript}}== |
||
The "nth prime" calculation here's gleaned from the Python and Julia solutions and the limitations to marking partly from the Phix. |
|||
<lang applescript>on sieveOfSundaram(indexRange) |
<lang applescript>on sieveOfSundaram(indexRange) |
||
if (indexRange's class is list) then |
if (indexRange's class is list) then |
||
Line 99: | Line 101: | ||
end script |
end script |
||
-- 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} |
||
-- |
-- Build a list of 'true's corresponding to the unmarked start numbers implied by the |
||
-- 1-based indices. The Python and Julia solutions note that the nth prime is approximately |
|||
-- but the number from which it'll be |
-- n * 1.2 * log(n), but the number from which it'll be derived is only about half that. |
||
-- 15 is added too here to ensure headroom |
-- 15 is added too here to ensure headroom 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 |
||
set len to 1500 |
set len to 1500 |
||
Line 115: | Line 116: | ||
end repeat |
end repeat |
||
-- Since it's a given that every third slot from 4 on will be "marked" (changed to false), there'll be |
|||
-- Apply the sieve, storing generated primes in consecutive slots from the beginning of the list. |
|||
-- no need to check these and thus no point in actually marking them! Skip the step = 3 marking sweep |
|||
-- Slots whose index mod 3 is 1 aren't tested, since, except for 1 itself, they're assumed to be |
|||
-- and the first slot of every three for marking in the subsequent sweeps. |
|||
-- "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, |
|||
-- Like the Phix solution, mark only from half the square of the step size, but adjusted |
|||
-- although it'll probably get marked incidentally in sweeps based on other intervals. |
|||
-- to sync the repeat to the second slot in each group of three for marking. |
|||
set step to 1 |
|||
repeat with j from (step * step div 2 - (step * 2 mod 3) * step + step) to (limit - step) by (step * 3) |
|||
⚫ | |||
⚫ | |||
⚫ | |||
end repeat |
|||
-- Calculate the primes from the indices of the unmarked slots |
|||
-- and store them in the list from the beginning. |
|||
set i to 1 |
set i to 1 |
||
set item i of o's lst to |
set item i of o's lst to i * 2 + 1 |
||
repeat with n from 2 to limit by 3 |
repeat with n from 2 to limit by 3 |
||
if (item n of o's lst) then |
if (item n of o's lst) then |
||
set i to i + 1 |
set i to i + 1 |
||
set item i of o's lst to |
set item i of o's lst to n * 2 + 1 |
||
⚫ | |||
end if |
end if |
||
if (item (n + 1) of o's lst) then |
if (item (n + 1) of o's lst) then |
||
set i to i + 1 |
set i to i + 1 |
||
set item i of o's lst to n |
set item i of o's lst to n * 2 + 3 -- ((n + 1) * 2) + 1) |
||
if (i = n2) then exit repeat |
|||
end if |
end if |
||
⚫ | |||
set step to step + 2 |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
end repeat |
end repeat |
||
-- set beginning of o's lst to 2 -- Uncomment if required. |
-- set beginning of o's lst to 2 -- Uncomment if required. |
||
Line 144: | Line 149: | ||
end sieveOfSundaram |
end sieveOfSundaram |
||
-- Task code: |
|||
on join(lst, delim) |
on join(lst, delim) |
||
set astid to AppleScript's text item delimiters |
set astid to AppleScript's text item delimiters |
||
Line 168: | Line 174: | ||
end task |
end task |
||
task()</lang> |
task()></lang> |
||
{{output}} |
{{output}} |