Rosetta Code

The sieve of Sundaram: Difference between revisions

Page Discussion

The sieve of Sundaram (view source)

Revision as of 08:32, 15 August 2021

277 bytes added ,  2 years ago
m
→‎{{header|AppleScript}}: Yet another optimisation and attendant comment work.
m (→‎{{header|AppleScript}}: Optimisation better explained in the comments.)
m (→‎{{header|AppleScript}}: Yet another optimisation and attendant comment work.)
Line 86:
 
=={{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)
if (indexRange's class is list) then
Line 99 ⟶ 101:
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}
-- TheBuild Pythona andlist Juliaof solutions'true's notecorresponding thatto the nthunmarked primestart isnumbers approximplied nby * 1.2 * log(n),the
-- 1-based indices. The Python and Julia solutions note that the nth prime is approximately
-- n * 1.2 * log(n), but the number from which it'll be generatedderived is only about half that.
-- 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 len to 1500
Line 115 ⟶ 116:
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
repeat with jstep from 5 to (n(limit +* 2 + step) to^ (limit0.5 -as stepinteger) by step * 32▼
-- 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)
set item j of o's lst to marked▼
set item (j + step) of o's lst to marked▼
end repeat▼
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 item i of o's lst to 3i * 2 + 1
repeat with n from 2 to limit by 3
if (item n of o's lst) then
set i to i + 1
set item i of o's lst to n + n + 1 -- (n * 2 + 1)
if (i ≥= n2) then exit repeat -- Enough primes obtained.▼
end if
if (item (n + 1) of o's lst) then
set i to i + 1
set item i of o's lst to n +* n2 + 3 -- ((n + 1) * 2) + 1)
if (i = n2) then exit repeat
end if
▲ 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
▲ set item (j + step) of o's lst to marked
▲ end repeat
end repeat
-- set beginning of o's lst to 2 -- Uncomment if required.
Line 144 ⟶ 149:
end sieveOfSundaram
 
-- Task code:
on join(lst, delim)
set astid to AppleScript's text item delimiters
Line 168 ⟶ 174:
end task
 
task()></lang>
 
{{output}}
Nig
557

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/314837"