Ramanujan primes: Difference between revisions
→{{header|Wren}}: Replaced existing solution with an infinitely faster one.
(Replaced Phix algorithm by C++ algorithm which precomputes the values of the pi function. Added the 100_000th Ramanujan prime.) |
(→{{header|Wren}}: Replaced existing solution with an infinitely faster one.) |
||
Line 516:
=={{header|Wren}}==
{{
{{libheader|Wren-seq}}
{{libheader|Wren-fmt}}
<br>
▲{{libheader|Wren-sort}}
This takes about
<lang ecmascript>import "/
import "/seq" for Lst
import "/fmt" for Fmt
var count
var
count = List.filled(limit, 1)
if (limit > 0) count[0] = 0
for (i in Stepped.new(4...limit, 2)) count[i] = 0
var p = 3
if (delta <= n) return primes[pi]▼
var
while (sq < limit) {
if (count[p] != 0) {
var q = sq
while (q < limit) {
count[q] = 0
q = q + p * 2
}
}
sq = sq + (p + 1) * 4
p = p + 2
}
var sum = 0
for (i in 0...limit) {
sum = sum + count[i]
count[i] = sum
}
}
var primeCount = Fn.new { |n| (n < 1) ? 0 : count[n] }
var ramanujanMax = Fn.new { |n| (4 * n * (4*n).log).ceil }
var ramanujanPrime = Fn.new { |n|
for (i in ramanujanMax.call(n)..2*n) {
if (i % 2 == 1) continue
if (primeCount.call(i) - primeCount.call((i/2).floor) < n) return i + 1
}
return 0
}
primeCounter.call(1 + ramanujanMax.call(1e6))
System.print("The first 100 Ramanujan primes are:")
var rams = (1..100).map { |n|
for (chunk in Lst.chunks(rams, 10)) Fmt.print("$,5d", chunk)
Fmt.print("\nThe 1,000th Ramanujan prime is $,6d",
Fmt.print("\nThe 10,000th Ramanujan prime is $,7d",
Fmt.print("\nThe 100,000th Ramanujan prime is $,9d", ramanujanPrime.call(100000))
Fmt.print("\nThe 1,000,000th Ramanujan prime is $,10d", ramanujanPrime.call(1000000))</lang>
{{out}}
<pre>
The first 100 Ramanujan primes are:
2 11 17 29 41 47 59 67 71 97
101 107 127 149 151 167 179 181 227 229
233 239 241 263 269 281 307 311 347 349
367 373 401 409 419 431 433 439 461 487
491 503 569 571 587 593 599 601 607 641
643 647 653 659 677 719 727 739 751 769
809 821 823 827 853 857 881 937 941 947
967 983 1,009 1,019 1,021 1,031 1,049 1,051 1,061 1,063
1,087 1,091 1,097 1,103 1,151 1,163 1,187 1,217 1,229 1,249
1,277 1,289 1,297 1,301 1,367 1,373 1,423 1,427 1,429 1,439
The 1,000th Ramanujan prime is 19,403
The 10,000th Ramanujan prime is 242,057
The 100,000th Ramanujan prime is 2,916,539
The 1,000,000th Ramanujan prime is 34,072,993
</pre>
|