Project Euler – Problem 60

Problem 60:
The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime.

For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property.

Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.

import java.math.BigInteger;
import java.util.Vector;
 
class runner2
{	
	//3 [11 13 17 19 23 29 31 37 41 43 47 53]
	//11 [13 17 23 29 31 37 41 43 47 53]
	private static Vector<BigInteger> parseSet(Vector<BigInteger> currentSet, int currentCount) {
		if(currentSet.size() <= 1) return currentSet;
 
		Vector<BigInteger> result = new Vector<BigInteger>();
		int biggestSize = 0;
		for(int i=0; i<currentSet.size()-1 ;i++){
			Vector<BigInteger> subSet = new Vector<BigInteger>();			
			for(int j=i+1; j<currentSet.size() ;j++){
				BigInteger bij = new BigInteger(currentSet.get(i).toString() + currentSet.get(j).toString());
				BigInteger bji = new BigInteger(currentSet.get(j).toString() + currentSet.get(i).toString());
 
				if(!bij.isProbablePrime(100) || !bji.isProbablePrime(100)) continue;
 
				subSet.add(currentSet.get(j));
			}
			//Requires at least (3 + filter + "i" on first pass) elements.
			//Before passing in the residual set.
			if(subSet.size() < currentCount-1) continue;
			//Parse the Subset...
			subSet = parseSet(subSet, currentCount-1);
 
			//Again we need to check the size of the subset to ensure we have enough values to return
			if(subSet.size() < currentCount-1) continue;//ignore... unfortunately
 
			if(biggestSize < subSet.size()){
				biggestSize = subSet.size();
				subSet.add(currentSet.get(i));
				result = subSet;
			}
		}
		return result;
	}
 
	public static void main (String[] args) throws java.lang.Exception
	{
		long time = System.currentTimeMillis();
 
		int limit = 5;
 
		for(int i=3;i<50;i++){//1000000
			BigInteger bi = new BigInteger(""+i);
			if(!bi.isProbablePrime(100)) continue;
 
			Vector<BigInteger> validOnes = new Vector<BigInteger>(500);
			for(int j=i+1; j<10000; j++){//1000000
				BigInteger bj = new BigInteger(""+j);
				if(!bj.isProbablePrime(100)) continue;
 
				String ij = ""+i+j, ji = ""+j+i;
				BigInteger bij = new BigInteger(ij), bji = new BigInteger(ji);
				if(!bij.isProbablePrime(100) || !bji.isProbablePrime(100)) continue;
 
				validOnes.add(bj);
			}
 
			if(validOnes.size() < limit) continue;//Requires at least five elements
			//Begin cyclical parsing..
			Vector<BigInteger> result = parseSet(validOnes, limit-1);
			if(result.size() == limit-1){
				int sum = 0;
				result.add(bi);
				for(BigInteger a : result){
					sum += a.intValue();
					System.out.println(a);
				}
				System.out.println("sum: "+sum);
				break;
			}
		}
 
		System.out.println("time: "+(System.currentTimeMillis() - time));
	}
}


Note: Unfortunately, the solution didn’t come to me quickly (took 3-4 days), which is why “parseSet” is a pretty ugly mess.