The sieve of Sundaram: Difference between revisions
Added Wren
m (Added Wikipedia reference) |
(Added Wren) |
||
Line 103:
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>
| |||