104 lines
3.1 KiB
Java
104 lines
3.1 KiB
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));
|
|
}
|
|
|
|
}
|