Anonymous user
Ramanujan primes: Difference between revisions
→{{header|Nim}}
m (→{{header|Go}}: Typos copied from Wren.) |
|||
Line 137:
The 10,000th Ramanujan prime is 242057
</pre>
=={{header|Nim}}==
{{trans|Phix}}
This is a straight translation of Phix version, but I had to add some code to manage prime numbers. Note also that in Nim sequences starts at index 0, not 1.
I compiled using command <code>nim c -d:release -d:lto ramanujan_primes.nim</code>, i.e. with runtime checks on and link time optimization. The program runs in about 35 ms on my laptop (i5-8250U CPU @ 1.60GHz, 8 GB Ram, Linux Manjaro). Fast, but this is normal for native code.
<lang Nim>import algorithm, math, strutils, times
let t0 = now()
const N = 400_000
var composite: array[2..N, bool]
for n in 2..N:
let n2 = n * n
if n2 > N: break
if not composite[n]:
for k in countup(n2, N, n):
composite[k] = true
proc primesLe(n: int): seq[int] =
for i, comp in composite:
if i > n: break
if not comp: result.add i
var piCache: seq[int]
proc pi(n: int): int =
if n == 0: return 0
if n > piCache.len:
let primes = primesLe(n)
for i in piCache.len+1..n:
let k = primes.upperBound(i)
piCache.add k
result = piCache[n-1]
proc ramanujanPrime(n: int): int =
let maxPoss = int(ceil(4 * n.toFloat * ln(4 * n.toFloat)))
for i in countdown(maxPoss, 1):
if pi(i) - pi(i div 2) < n:
return i + 1
for n in 1..100:
stdout.write ($ramanujanPrime(n)).align(4), if n mod 20 == 0: '\n' else: ' '
echo "\nThe 1000th Ramanujan prime is ", ramanujanPrime(1000)
echo "The 10000th Ramanujan prime is ", ramanujanPrime(10000)
echo "\nElapsed time: ", (now() - t0).inMilliseconds, " ms"</lang>
{{out}}
<pre> 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 1009 1019 1021 1031 1049 1051 1061 1063
1087 1091 1097 1103 1151 1163 1187 1217 1229 1249 1277 1289 1297 1301 1367 1373 1423 1427 1429 1439
The 1000th Ramanujan prime is 19403
The 10000th Ramanujan prime is 242057
Elapsed time: 34 ms</pre>
=={{header|Phix}}==
| |||