### Consecutive prime sum题号：50 难度： 5 中英对照

The prime 41, can be written as the sum of six consecutive primes:

41 = 2 + 3 + 5 + 7 + 11 + 13

### Code

public final class p50 {
private static final int LIMIT=(int)Math.pow(10, 6);
//private static final int LIMIT=16000;
public static void main(String[] args){
long start=System.nanoTime();
long result = run();
long end=System.nanoTime();
System.out.println(result);
System.out.println( (end-start)/1000000 + "ms" );
}
public static long run(){
boolean[] isPrime = listPrimality(LIMIT);
int[] primes = listPrimes(LIMIT);

long maxSum = 0;
int maxRun = -1;
for (int i = 0; i < primes.length; i++) {  // For each index of a starting prime number
int sum = 0;
for (int j = i; j < primes.length; j++) {  // For each end index (inclusive)
sum += primes[j];
if (sum > LIMIT)
break;
else if (j - i > maxRun && sum > maxSum && isPrime[sum]) {
maxSum = sum;
maxRun = j - i;
}
}
}
return maxSum;
}

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;
int end =(int) Math.sqrt(n);
for (int i = 3 ; i <= end; i += 2) {
if (result[i]) {
for (int j = i * i; j <= n; j += i << 1)
result[j] = false;
}
}
return result;
}
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;
}

}

997651
32ms