The sieve of Sundaram: Difference between revisions

Content added Content deleted
m (→‎{{header|REXX}}: changed the whitespace in the REXX section header.)
m (→‎{{header|AppleScript}}: Further optimised by only marking two out of every three "numbers" in each sweep. Minor cosmetic changes.)
Line 86: Line 86:


=={{header|AppleScript}}==
=={{header|AppleScript}}==
<lang applescript>on sieveOfSundaram(range)
<lang applescript>on sieveOfSundaram(indexRange)
if (range's class is list) then
if (indexRange's class is list) then
set n1 to beginning of range
set n1 to beginning of indexRange
set n2 to end of range
set n2 to end of indexRange
else
else
set n1 to range
set n1 to indexRange
set n2 to range
set n2 to indexRange
end if
end if
Line 99: Line 99:
end script
end script
-- Build a list of at least as many 'true's as there are initially unmarked numbers from which
-- Build a list of at least as many 'true's as there are notionally initially
-- the primes will be calculated. The numbers themselves are implied by their indices.
-- unmarked numbers. The numbers themselves are implied by the 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's derived will be about half that.
-- but the number from which it'll be derived is about half that.
-- 2 is added here to ensure headroom for 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 & ") + 2'| 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
repeat len times
repeat len times
Line 115: Line 115:
end repeat
end repeat
-- Apply the sieve, storing derived 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.
set step to 1
set step to 1
set i to 1
set i to 1
Line 122: Line 122:
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 n * 2 + 1
set item i of o's lst to n + n + 1 -- (n * 2 + 1)
end if
end if
tell (n + 1) to if (item it 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 it * 2 + 1
set item i of o's lst to n + n + 3 -- ((n + 1) * 2 + 1)
end if
end if
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
repeat with j from (n + 2 + step) to limit by step
-- 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
set item j of o's lst to marked
set item j of o's lst to marked
set item (j + step) of o's lst to marked
end repeat
end repeat
end repeat
end repeat
Retrieved from "https://rosettacode.org/wiki/The_sieve_of_Sundaram"