### Investigating a Prime Pattern 题号：146 难度： 50 中英对照

The smallest positive integer n for which the numbers n2+1, n2+3, n2+7, n2+9, n2+13, and n2+27 are consecutive primes is 10. The sum of all such integers n below one-million is 1242490.

What is the sum of all such integers n below 150 million?

### Code

public final class p146 {
public static void main(String[] args) {
long start=System.nanoTime();
String result = run();
long end=System.nanoTime();
System.out.println(result);
System.out.println( (end-start)/1000000 + "ms" );
}

private static final int LIMIT = 150000000;
private static long[] INCREMENTS = {1, 3, 7, 9, 13, 27};  // Must be in non-decreasing orde

static public String run() {
long sum = 0;
for (int n = 0; n < LIMIT; n += 10) {
if (hasConsecutivePrimes(n))
sum += n;
}
return Long.toString(sum);
}

private static long maxNumber = (long)LIMIT * LIMIT + INCREMENTS[INCREMENTS.length - 1];
private static int[] primes = listPrimes((int)(Math.sqrt(maxNumber)+1e-8));

private static boolean hasConsecutivePrimes(int n) {
// Generate the set of numbers to test for primality
long n2 = (long)n * n;
long[] temp = new long[INCREMENTS.length];
for (int i = 0; i < INCREMENTS.length; i++)
temp[i] = n2 + INCREMENTS[i];

// Test that each number is prime.
// Note: The nesting of the loops can be reversed, but this way is much faster.
for (int p : primes) {
for (long x : temp) {
if (x != p && x % p == 0)
return false;
}
}

// Test that each number that is not an increment is composite.
for (int i = 1; i < INCREMENTS[INCREMENTS.length - 1]; i++) {
if (java.util.Arrays.binarySearch(INCREMENTS, i) < 0 && isPrime(n2 + i))
return false;
}
return true;
}

private static boolean isPrime(long n) {
int end = (int)(Math.sqrt(n)+1e-8);
for (int p : primes) {
if (p > end)
break;
if (n != p && n % p == 0)
return false;
}
return true;
}

// Returns a Boolean array 'isPrime' where isPrime[i] indicates whether i is prime, for 0 <= i <= n.
// For a large batch of queries, this is faster than calling isPrime() for each integer.
// For example: listPrimality(100) = {false, false, true, true, false, true, false, true, false, false, ...} (array length 101).
public static boolean[] listPrimality(int n) {
if (n < 0)
throw new IllegalArgumentException("Negative array size");
boolean[] result = new boolean[n + 1];
if (n >= 2)
result[2] = true;
for (int i = 3; i <= n; i += 2)
result[i] = true;
// Sieve of Eratosthenes
for (int i = 3, end = (int)(Math.sqrt(n)+1e-8); i <= end; i += 2) {
if (result[i]) {
// Note: i * i does not overflow
for (int j = i * i; j <= n; j += i << 1)
result[j] = false;
}
}
return result;
}

// Returns all the prime numbers less than or equal to n, in ascending order.
// For example: listPrimes(97) = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ..., 83, 89, 97}.
public static int[] listPrimes(int n) {
boolean[] isprime = listPrimality(n);
int count = 0;
for (boolean b : isprime) {
if (b)
count++;
}

int[] result = new int[count];
for (int i = 0, j = 0; i < isprime.length; i++) {
if (isprime[i]) {
result[j] = i;
j++;
}
}
return result;
}

}
676333270
95246ms