当前位置:首页 » Project Euler » 详细页

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

Solution

此题思路是 有两个变量,一个maxRun记录连续质数的长度,一个maxSum记录总和 从第1个质数2开始(直到10^6),依次与后续的连续质数相加,判断和是否为质数,若是质数且连续质数长度和总和分别大于maxRun和maxSum的情况下,更新maxRun和maxSum的值

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