a Programmer's blog

Problem 37: The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.

Find the sum of the only eleven primes that are both truncatable from left to right and right to left.

NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.

class runner
{
	private static void primeSieve(boolean[] primes){
		for(int i=2;i= primes.length) break;
				primes[prod] = false;
			}
		}
	}
 
	private static boolean truncRightAndLeft(int n, boolean[] primes){
		int i=n/10; int len=1;
		while(i>0){
			if(!primes[i]) return false;
			len++;
			i/=10;
		}
		
		for(i=len-1;i>0;i--){
			n = (int) (n % Math.pow(10,i));
			if(!primes[n]) return false;
		}
		
		return true;
	}

	public static void main (String[] args) throws java.lang.Exception
	{
		long time = System.currentTimeMillis();
 
		int limit = 1000000;//hint is 11, so we can trial and error for the limit
		boolean[] primes = new boolean[limit+1];
		for(int i=2;i