The sieve of Sundaram: Difference between revisions

=={{header|AppleScript}}==

<lang applescript>on sieveOfSundaram(range)

if (range's class is list) then

set n1 to beginning of range

set n2 to end of range

else

set n1 to range

set n2 to range

end if

script o

property lst : {}

end script

-- Build a list of at least as many 'true's as there are initially unmarked numbers from which

-- the primes will be calculated. The numbers themselves are implied by their indices.

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's derived will be about half that.

-- 2 is added here to ensure headroom for lower prime counts.

set limit to (do shell script "echo '" & n2 & " * 0.6 * l(" & n2 & ") + 2'| bc -l") as integer

set len to 1500

repeat len times

set end of o's lst to unmarked

end repeat

repeat while (len < limit)

set o's lst to o's lst & o's lst

set len to len + len

end repeat

-- Apply the sieve, replacing surviving 'true's in the list with their index * 2 + 1.

set step to 1

set item 1 of o's lst to 3

repeat with n from 2 to limit by 3

if (item n of o's lst) then set item n of o's lst to n * 2 + 1

tell (n + 1) to if (item it of o's lst) then set item it of o's lst to it * 2 + 1

set step to step + 2

repeat with j from (n + 2 + step) to limit by step

set item j of o's lst to marked

end repeat

end repeat

-- set beginning of o's lst to 2 -- Uncomment if needed.

return o's lst's numbers n1 thru n2

end sieveOfSundaram

on join(lst, delim)

set astid to AppleScript's text item delimiters

set AppleScript's text item delimiters to delim

set txt to lst as text

set AppleScript's text item delimiters to astid

return txt

end join

on task()

--set r1 to sieveOfSundaram({1, 100})

--set r2 to sieveOfSundaram(1000000)

set r to sieveOfSundaram({1, 1000000})

set r1 to items 1 thru 100 of r

set r2 to item 1000000 of r

set output to {"1st to 100th Sundaram primes:"}

repeat with i from 1 to 100 by 10

set end of output to join(items i thru (i + 9) of r1, " ")

end repeat

set end of output to "1,000,000th: "

set end of output to r2

return join(output, linefeed)

end task

task()</lang>

{{output}}

<lang applescript>"1st to 100th Sundaram primes:

3 5 7 11 13 17 19 23 29 31

37 41 43 47 53 59 61 67 71 73

79 83 89 97 101 103 107 109 113 127

131 137 139 149 151 157 163 167 173 179

181 191 193 197 199 211 223 227 229 233

239 241 251 257 263 269 271 277 281 283

293 307 311 313 317 331 337 347 349 353

359 367 373 379 383 389 397 401 409 419

421 431 433 439 443 449 457 461 463 467

479 487 491 499 503 509 521 523 541 547

1,000,000th:

15485867"</lang>