Ramanujan primes: Difference between revisions
Added Java solution
Thundergnat (talk | contribs) (→{{header|Raku}}: Add a Raku example) |
(Added Java solution) |
||
Line 182:
Took 946.193311ms
</pre>
=={{header|Java}}==
{{trans|C++}}
<lang java>import java.text.NumberFormat;
import java.util.Arrays;
public class RamanujanPrimes {
public static void main(String[] args) {
NumberFormat nf = NumberFormat.getInstance();
long start = System.nanoTime();
System.out.println("First 100 Ramanujan primes:");
PrimeCounter pc = new PrimeCounter(1 + ramanujanMax(100000));
for (int i = 1; i <= 100; ++i) {
int p = ramanujanPrime(pc, i);
System.out.printf("%5s%c", nf.format(p), i % 10 == 0 ? '\n' : ' ');
}
System.out.println();
for (int i = 1000; i <= 100000; i *= 10) {
int p = ramanujanPrime(pc, i);
System.out.printf("The %sth Ramanujan prime is %s.\n",
nf.format(i), nf.format(p));
}
long end = System.nanoTime();
System.out.printf("\nElapsed time: %.1f milliseconds\n", (end - start) / 1e6);
}
private static int ramanujanMax(int n) {
return (int)Math.ceil(4 * n * Math.log(4 * n));
}
private static int ramanujanPrime(PrimeCounter pc, int n) {
for (int i = ramanujanMax(n); i >= 0; --i) {
if (pc.primeCount(i) - pc.primeCount(i / 2) < n)
return i + 1;
}
return 0;
}
private static class PrimeCounter {
private PrimeCounter(int limit) {
count = new int[limit];
Arrays.fill(count, 1);
if (limit > 0)
count[0] = 0;
if (limit > 1)
count[1] = 0;
for (int i = 4; i < limit; i += 2)
count[i] = 0;
for (int p = 3, sq = 9; sq < limit; p += 2) {
if (count[p] != 0) {
for (int q = sq; q < limit; q += p << 1)
count[q] = 0;
}
sq += (p + 1) << 2;
}
Arrays.parallelPrefix(count, (x, y) -> x + y);
}
private int primeCount(int n) {
return n < 1 ? 0 : count[n];
}
private int[] count;
}
}</lang>
{{out}}
<pre>
First 100 Ramanujan primes:
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.
Elapsed time: 187.2 milliseconds
</pre>
| |||