Ramanujan primes/twins: Difference between revisions
New post.
(Added Sidef) |
(New post.) |
||
Line 132:
There are 74,973 twins in the first 1,000,000 Ramanujan primes.
Took 699.967994ms
</pre>
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public final class RamanujanPrimesTwins {
public static void main(String[] aArgs) {
final int limit = 1_000_000;
final int[] primePi = initialisePrimePi(ramanujanMaximum(limit) + 1);
final int millionthRamanujanPrime = ramanujanPrime(primePi, limit);
System.out.println("The 1_000_000th Ramanujan prime is " + millionthRamanujanPrime);
List<Integer> primes = listPrimesLessThan(millionthRamanujanPrime);
int[] ramanujanPrimeIndexes = new int[primes.size()];
for ( int i = 0; i < ramanujanPrimeIndexes.length; i++ ) {
ramanujanPrimeIndexes[i] = primePi[primes.get(i)] - primePi[primes.get(i) / 2];
}
int lowerLimit = ramanujanPrimeIndexes[ramanujanPrimeIndexes.length - 1];
for ( int i = ramanujanPrimeIndexes.length - 2; i >= 0; i-- ) {
if ( ramanujanPrimeIndexes[i] < lowerLimit ) {
lowerLimit = ramanujanPrimeIndexes[i];
} else {
ramanujanPrimeIndexes[i] = 0;
}
}
List<Integer> ramanujanPrimes = new ArrayList<Integer>();
for ( int i = 0; i < ramanujanPrimeIndexes.length; i++ ) {
if ( ramanujanPrimeIndexes[i] != 0 ) {
ramanujanPrimes.add(primes.get(i));
}
}
int twinsCount = 0;
for ( int i = 0; i < ramanujanPrimes.size() - 1; i++ ) {
if ( ramanujanPrimes.get(i) + 2 == ramanujanPrimes.get(i + 1) ) {
twinsCount += 1;
}
}
System.out.println("There are " + twinsCount + " twins in the first " + limit + " Ramanujan primes.");
}
private static List<Integer> listPrimesLessThan(int aLimit) {
boolean[] composite = new boolean[aLimit + 1];
int n = 3;
int nSquared = 9;
while ( nSquared <= aLimit ) {
if ( ! composite[n] ) {
for ( int k = nSquared; k < aLimit; k += 2 * n ) {
composite[k] = true;
}
}
nSquared += ( n + 1 ) << 2;
n += 2;
}
List<Integer> result = new ArrayList<Integer>();
result.add(2);
for ( int i = 3; i < aLimit; i += 2 ) {
if ( ! composite[i] ) {
result.add(i);
}
}
return result;
}
private static int ramanujanPrime(int[] aPrimePi, int aNumber) {
int maximum = ramanujanMaximum(aNumber);
if ( ( maximum & 1) == 1 ) {
maximum -= 1;
}
int index = maximum;
while ( aPrimePi[index] - aPrimePi[index / 2] >= aNumber ) {
index -= 1;
}
return index + 1;
}
private static int[] initialisePrimePi(int aLimit) {
int[] result = new int[aLimit];
Arrays.fill(result, 1);
result[0] = 0;
result[1] = 0;
for ( int i = 4; i < aLimit; i += 2 ) {
result[i] = 0;
}
for ( int p = 3, square = 9; square < aLimit; p += 2 ) {
if ( result[p] != 0 ) {
for ( int q = square; q < aLimit; q += p << 1 ) {
result[q] = 0;
}
}
square += ( p + 1 ) << 2;
}
Arrays.parallelPrefix(result, Integer::sum);
return result;
}
private static int ramanujanMaximum(int aNumber) {
return (int) Math.ceil(4 * aNumber * Math.log(4 * aNumber));
}
}
</syntaxhighlight>
{{ out }}
<pre>
The 1_000_000th Ramanujan prime is 34072993
There are 74973 twins in the first 1000000 Ramanujan primes.
</pre>
| |||