Ramanujan primes: Difference between revisions
Content added Content deleted
(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: | Line 516: | ||
=={{header|Wren}}== |
=={{header|Wren}}== |
||
{{ |
{{trans|C++}} |
||
| ⚫ | |||
{{libheader|Wren-seq}} |
{{libheader|Wren-seq}} |
||
{{libheader|Wren-fmt}} |
{{libheader|Wren-fmt}} |
||
<br> |
|||
| ⚫ | |||
This takes about |
This takes about 1.1 seconds to find the 100,000th Ramanujan prime on my machine. The millionth takes 13.2 seconds. |
||
<lang ecmascript>import "/ |
<lang ecmascript>import "/trait" for Stepped |
||
import "/seq" for Lst |
import "/seq" for Lst |
||
import "/fmt" for Fmt |
import "/fmt" for Fmt |
||
import "/sort" for Find |
|||
var count |
|||
var primes = Int.primeSieve(700000) // say |
|||
var |
var primeCounter = Fn.new { |limit| |
||
count = List.filled(limit, 1) |
|||
var max = (4 * n * (4 * n).log / 2.log).floor |
|||
if (limit > 0) count[0] = 0 |
|||
var pi = Find.all(primes[2*n..-1], max)[2].from // binary search from min of (2n)th prime |
|||
if (limit > 1) count[1] = 0 |
|||
for (i in Stepped.new(4...limit, 2)) count[i] = 0 |
|||
var delta = pi + 1 - Int.primeCount((primes[pi]/2).floor) |
|||
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| |
|||
| ⚫ | |||
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:") |
System.print("The first 100 Ramanujan primes are:") |
||
var rams = (1..100).map { |n| |
var rams = (1..100).map { |n| ramanujanPrime.call(n) }.toList |
||
for (chunk in Lst.chunks(rams, 10)) Fmt.print("$,5d", chunk) |
for (chunk in Lst.chunks(rams, 10)) Fmt.print("$,5d", chunk) |
||
Fmt.print("\nThe 1,000th Ramanujan prime is $,6d", |
Fmt.print("\nThe 1,000th Ramanujan prime is $,6d", ramanujanPrime.call(1000)) |
||
Fmt.print("\nThe 10,000th Ramanujan prime is $,7d", |
Fmt.print("\nThe 10,000th Ramanujan prime is $,7d", ramanujanPrime.call(10000)) |
||
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}} |
{{out}} |
||
<pre> |
<pre> |
||
The first 100 Ramanujan primes are: |
The first 100 Ramanujan primes are: |
||
2 11 17 29 41 47 59 67 71 97 |
2 11 17 29 41 47 59 67 71 97 |
||
101 107 127 149 151 167 179 181 227 229 |
101 107 127 149 151 167 179 181 227 229 |
||
233 239 241 263 269 281 307 311 347 349 |
233 239 241 263 269 281 307 311 347 349 |
||
367 373 401 409 419 431 433 439 461 487 |
367 373 401 409 419 431 433 439 461 487 |
||
491 503 569 571 587 593 599 601 607 641 |
491 503 569 571 587 593 599 601 607 641 |
||
643 647 653 659 677 719 727 739 751 769 |
643 647 653 659 677 719 727 739 751 769 |
||
809 821 823 827 853 857 881 937 941 947 |
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 |
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,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 |
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 1,000th Ramanujan prime is 19,403 |
||
The 10,000th Ramanujan prime is 242,057 |
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> |
</pre> |
||