The sieve of Sundaram: Difference between revisions
Content added Content deleted
m (Added Wikipedia reference) |
(Added Wren) |
||
Line 103: | Line 103: | ||
The millionth Sundaram prime is 15_485_867</pre> |
The millionth Sundaram prime is 15_485_867</pre> |
||
=={{header|Wren}}== |
|||
{{libheader|Wren-fmt}} |
|||
{{libheader|Wren-seq}} |
|||
I've worked here from the second (optimized) Python example in the Wikipedia article for SOS which allows an easy transition to an 'odds only' SOE for comparison. |
|||
<lang ecmascript>import "/fmt" for Fmt |
|||
import "/seq" for Lst |
|||
var sos = Fn.new { |n| |
|||
if (n < 3) return [] |
|||
var primes = [] |
|||
var k = ((n-3)/2).floor + 1 |
|||
var marked = List.filled(k, true) |
|||
var limit = ((n.sqrt.floor - 3)/2).floor + 1 |
|||
limit = limit.max(0) |
|||
for (i in 0...limit) { |
|||
var p = 2*i + 3 |
|||
var s = ((p*p - 3)/2).floor |
|||
var j = s |
|||
while (j < k) { |
|||
marked[j] = false |
|||
j = j + p |
|||
} |
|||
} |
|||
for (i in 0...k) { |
|||
if (marked[i]) primes.add(2*i + 3) |
|||
} |
|||
return primes |
|||
} |
|||
// odds only |
|||
var soe = Fn.new { |n| |
|||
if (n < 3) return [] |
|||
var primes = [] |
|||
var k = ((n-3)/2).floor + 1 |
|||
var marked = List.filled(k, true) |
|||
var limit = ((n.sqrt.floor - 3)/2).floor + 1 |
|||
limit = limit.max(0) |
|||
for (i in 0...limit) { |
|||
if (marked[i]) { |
|||
var p = 2*i + 3 |
|||
var s = ((p*p - 3)/2).floor |
|||
var j = s |
|||
while (j < k) { |
|||
marked[j] = false |
|||
j = j + p |
|||
} |
|||
} |
|||
} |
|||
for (i in 0...k) { |
|||
if (marked[i]) primes.add(2*i + 3) |
|||
} |
|||
return primes |
|||
} |
|||
var limit = 16e6 // say |
|||
var start = System.clock |
|||
var primes = sos.call(limit) |
|||
var elapsed = ((System.clock - start) * 1000).round |
|||
Fmt.print("Using the Sieve of Sundaram generated primes up to $,d in $,d ms.\n", limit, elapsed) |
|||
System.print("First 100 odd primes generated by the Sieve of Sundaram:") |
|||
for (chunk in Lst.chunks(primes[0..99], 10)) Fmt.print("$3d", chunk) |
|||
Fmt.print("\nThe $,d Sundaram prime is $,d", 1e6, primes[1e6-1]) |
|||
start = System.clock |
|||
primes = soe.call(limit) |
|||
elapsed = ((System.clock - start) * 1000).round |
|||
Fmt.print("\nUsing the Sieve of Eratosthenes would have generated them in $,d ms.", elapsed) |
|||
Fmt.print("\nAs a check, the $,d Sundaram prime would again have been $,d", 1e6, primes[1e6-1])</lang> |
|||
{{out}} |
|||
<pre> |
|||
Using the Sieve of Sundaram generated primes up to 16,000,000 in 1,232 ms. |
|||
First 100 odd primes generated by the Sieve of Sundaram: |
|||
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 |
|||
The 1,000,000 Sundaram prime is 15,485,867 |
|||
Using the Sieve of Eratosthenes would have generated them in 797 ms. |
|||
As a check, the 1,000,000 Sundaram prime would again have been 15,485,867 |
|||
</pre> |