The sieve of Sundaram: Difference between revisions
Content added Content deleted
Line 569: | Line 569: | ||
421 431 433 439 443 449 457 461 463 467 |
421 431 433 439 443 449 457 461 463 467 |
||
479 487 491 499 503 509 521 523 541 547</pre> |
479 487 491 499 503 509 521 523 541 547</pre> |
||
=={{header|jq}}== |
|||
{{works with|jq}} |
|||
'''Works with gojq, the Go implementation of jq''' (*) |
|||
The hard part is anticipating how large the sieve must be to ensure |
|||
the n-th prime will be included. |
|||
Julia uses: (1.2 * nth * log(nth)) which is perhaps larger than always necessary. |
|||
Here we employ a naive adaptive approach. |
|||
(*) For large sieves, gojq will consume a very large amount of memory. |
|||
<lang jq># `sieve_of_Sundaram` as defined here generates the stream of |
|||
# consecutive primes from 3 on but less than or equal to the specified |
|||
# limit specified by `.`. |
|||
# input: an integer, n |
|||
# output: stream of consecutive primes from 3 but less than or equal to n |
|||
def sieve_of_Sundaram: |
|||
def idiv($b): (. - (. % $b))/$b ; |
|||
debug | |
|||
round as $n |
|||
| if $n < 2 then empty |
|||
else |
|||
((($n-3) | idiv(2)) + 1) as $k |
|||
| [range(0; $k + 1) | 1 ] # integers_list |
|||
| reduce range (0; (($n|sqrt) - 3) / 2 + 1) as $i (.; |
|||
(2*$i + 3) as $p |
|||
| ((($p*$p - 3) | idiv(2))) as $s |
|||
| reduce range($s; $k; $p) as $j (.; |
|||
if .[$j] then .[$j] = false else . end ) ) |
|||
| range(0; $k) as $i |
|||
| if .[$i] then ($i+1)*2+1 else empty end |
|||
end ; |
|||
# Emit an array of $n Sundaram primes. |
|||
# The first Sundaram prime is 3 so we ensure Sundaram_prime(1) is [3]. |
|||
# An adaptive definition to ensure generality without being excessively conservative. |
|||
def Sundaram_primes($n): |
|||
def sieve: |
|||
. as $in |
|||
| [limit($n; sieve_of_Sundaram)] |
|||
| if length == $n then . |
|||
else ($n + $in) as $m |
|||
| ("... nth_Sundaram_prime(\($n)): \($in) => \($m))" | debug) as $debug |
|||
| $m | sieve |
|||
end; |
|||
if $n < 1 then empty |
|||
elif $n <= 100 then ($n | 1.2 * . * log) | sieve |
|||
else $n | (1.15 * . * log) | sieve # OK |
|||
end;</lang> |
|||
'''For pretty-printing''' |
|||
<lang jq>def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .; |
|||
def nwise($n): |
|||
def n: if length <= $n then . else .[0:$n] , (.[$n:] | n) end; |
|||
n;</lang> |
|||
'''The Tasks''' |
|||
<lang jq>def hundred: |
|||
Sundaram_primes(100) |
|||
| nwise(10) |
|||
| map(lpad(3)) |
|||
| join(" "); |
|||
"First hundred:", hundred, |
|||
"\nMillionth is \(Sundaram_primes(1000000)[-1])"</lang> |
|||
{{out}} |
|||
<pre> |
|||
First hundred: |
|||
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 |
|||
Millionth is 15485867 |
|||
</pre> |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |