The sieve of Sundaram: Difference between revisions
Content added Content deleted
(→{{header|Ruby}}: Add Ruby) |
Alextretyak (talk | contribs) (Added 11l) |
||
Line 23: | Line 23: | ||
* The article on [[wp:Sieve_of_Sundaram|Wikipedia]]. |
* The article on [[wp:Sieve_of_Sundaram|Wikipedia]]. |
||
<br><br> |
<br><br> |
||
=={{header|11l}}== |
|||
{{trans|Python}} |
|||
<lang 11l>F sieve_of_Sundaram(nth, print_all = 1B) |
|||
‘ |
|||
The sieve of Sundaram is a simple deterministic algorithm for finding all the |
|||
prime numbers up to a specified integer. This function is modified from the |
|||
Wikipedia entry wiki/Sieve_of_Sundaram, to give primes to their nth rather |
|||
than the Wikipedia function that gives primes less than n. |
|||
’ |
|||
assert(nth > 0, ‘nth must be a positive integer’) |
|||
V k = Int((2.4 * nth * log(nth)) I/ 2) |
|||
V integers_list = [1B] * k |
|||
L(i) 1 .< k |
|||
V j = Int64(i) |
|||
L i + j + 2 * i * j < k |
|||
integers_list[Int(i + j + 2 * i * j)] = 0B |
|||
j++ |
|||
V pcount = 0 |
|||
L(i) 1 .. k |
|||
I integers_list[i] |
|||
pcount++ |
|||
I print_all |
|||
print(f:‘{2 * i + 1:4}’, end' ‘ ’) |
|||
I pcount % 10 == 0 |
|||
print() |
|||
I pcount == nth |
|||
print("\nSundaram primes start with 3. The "nth‘th Sundaram prime is ’(2 * i + 1)".\n") |
|||
L.break |
|||
sieve_of_Sundaram(100, 1B) |
|||
sieve_of_Sundaram(1000000, 0B)</lang> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
Sundaram primes start with 3. The 100th Sundaram prime is 547. |
|||
Sundaram primes start with 3. The 1000000th Sundaram prime is 15485867. |
|||
</pre> |
|||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |