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 parseSet(Vector currentSet, int currentCount) {
if(currentSet.size() <= 1) return currentSet;
Vector result = new Vector();
int biggestSize = 0;
for(int i=0; i subSet = new Vector();
for(int j=i+1; j validOnes = new Vector(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 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.