Project Euler – Problem 50

Problem 50: Which prime, below one-million, can be written as the sum of the most consecutive primes?

class runner
{
	//true means composite
	public static int sieveArray(boolean[] arr){
		int numOfPrimes = 0;
		arr[0] = true; arr[1] = true;
		for(int i=2;i<arr.length/2; i++){
			if(arr[i]) continue;
			int next = i+i;
			while(next < arr.length){
				arr[next] = true;
				numOfPrimes++;
				next += i;
			}
		}
		return numOfPrimes;
	}
 
	private static int[] convertArr(int num, boolean[] arr2){
		int[] arr = new int[num];
		int k = 0;
		for(int i=0;i<arr2.length;i++){
			if(!arr2[i]) arr[k++] = i; 
		}
		return arr;
	}
 
	public static void main (String[] args) throws java.lang.Exception
	{
		long time = System.currentTimeMillis();
 
		int l=0,lp=5;
 
		boolean[] arr = new boolean[1000000];
		int numOfPrimes = sieveArray(arr);
 
		int[] primes = convertArr(numOfPrimes, arr);//drops size from 1mil to around 78-79k
 
		int primesum = 0;
		int primeIdx = -1;
		for(int n=1; n<primes.length; n++){
			int nval = primes[n];
 
			while(primesum+primes[1+primeIdx] <= nval){
				primesum += primes[++primeIdx];
			}
 
			int curIdx = primeIdx;
			int cursum = primesum;
			for(int i=0; i<n; i++){
				int ival = primes[i];
				if(cursum == nval){
					if(l<(curIdx-i)){
						l = (curIdx-i);
						lp = nval;
					}
					//System.out.println("p:"+nval+" len:"+(curIdx-i)+" start:"+ival);
					break;
				}
				cursum-=ival;
				while(cursum < nval && curIdx+1 < n){
					cursum += primes[++curIdx];
				}
			}
		}
		System.out.println("lp:"+lp+" l:"+l);
 
		System.out.println("time: "+(System.currentTimeMillis() - time));
	}
}


Note: If using Vectors for the array “primes”, the execution time will increase from 34s to 2.8minutes.