Ramanujan primes/twins: Difference between revisions
Added Wren
m (→{{header|Phix}}: grammer) |
(Added Wren) |
||
Line 81:
There are 74,973 twins in the first 1,000,000 Ramanujan primes
"1 minute and 11s"
</pre>
=={{header|Wren}}==
{{libheader|Wren-trait}}
{{libheader|Wren-math}}
{{libheader|Wren-fmt}}
<br>
As calculating the first 1 million Ramanujan primes individually is out of the question, we follow the Phix entry's clever strategy here of which this is a partial translation.
The only reason this is faster than Phix (normally we'd be much slower) is because the basic Ramanujan code is a translation of the very fast C++ code for that task.
<lang ecmascript>import "/trait" for Stepped, Indexed
import "/math" for Int, Math
import "/fmt" for Fmt
var count
var primeCounter = Fn.new { |limit|
count = List.filled(limit, 1)
if (limit > 0) count[0] = 0
if (limit > 1) count[1] = 0
for (i in Stepped.new(4...limit, 2)) count[i] = 0
var p = 3
var sq = 9
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|
if (n == 1) return 2
for (i in ramanujanMax.call(n)..2) {
if (i % 2 == 1) continue
if (primeCount.call(i) - primeCount.call((i/2).floor) < n) return i + 1
}
return 0
}
var rpc = Fn.new { |p| primeCount.call(p) - primeCount.call((p/2).floor) }
for (limit in [1e5, 1e6]) {
var start = System.clock
primeCounter.call(1 + ramanujanMax.call(limit))
var rplim = ramanujanPrime.call(limit)
Fmt.print("The $,dth Ramanujan prime is $,d", limit, rplim)
var r = Int.primeSieve(rplim)
var c = r.map { |p| rpc.call(p) }.toList
var ok = c[-1]
for (i in c.count - 2..0) {
if (c[i] < ok) {
ok = c[i]
} else {
c[i] = 0
}
}
var ir = Indexed.new(r).where { |se| c[se.index] != 0 }.toList
var twins = 0
for (i in 0...ir.count-1) {
if (ir[i].value + 2 == ir[i+1].value) twins = twins + 1
}
Fmt.print("There are $,d twins in the first $,d Ramanujan primes.", twins, limit)
System.print("Took %(Math.toPlaces(System.clock -start, 2, 0)) seconds.\n")
}</lang>
{{out}}
<pre>
The 100,000th Ramanujan prime is 2,916,539
There are 8,732 twins in the first 100,000 Ramanujan primes.
Took 1.33 seconds.
The 1,000,000th Ramanujan prime is 34,072,993
There are 74,973 twins in the first 1,000,000 Ramanujan primes.
Took 15.75 seconds.
</pre>
| |||