Project Euler

Problem 37: Truncatable Primes

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.

The Catch

How to manipulate the digits of a number to check if it is prime truncatable.

The Light

Parsing the number into a String to manipulate the digits and then parsing it back to integers is an inefficient method. Observe the following:
3797 / 10 = 379
3797 / 100 = 37
3797 / 1000 = 3
Dividing the number by multiples of 10 truncates digits from the right.

3797 % 10 = 7
3797 % 100 = 97
3797 % 1000 = 797
Take a modulo of the number by multiples of 10 truncates digits from the left.

Use prime checking method in Problem 3 to determine primness.

The Code

public class Problem37
{
  public static void main(String[] args)
  {
    int count = 0;
    int sum = 0;
    int ten = 10;
    boolean leftTrunc = true;
    boolean rightTrunc = true;

    for(int n = 11; count != 11; n += 2)
    {
      if(isPrime(n))
      {
        while(ten < n)
        {
          if(!isPrime(n/ten))
    	  {
    	    leftTrunc = false;
            break;
    	  }
    	  if(!isPrime(n%ten))
    	  {
    	    rightTrunc = false;
    	    break;
    	  }
    	  ten *= 10;
        }
        if(leftTrunc && rightTrunc)
        {
          ++count;
    	  sum += n;
        }
      }
      leftTrunc = true;
      rightTrunc = true;
      ten = 10;
    }	  
    System.out.println("Sum = " + sum);
  }

  public static boolean isPrime(int n)
  {
    if( n < 2 )
      return false; 

    if(n % 2 == 0 && n != 2)
      return false;

    for( int i = 3; i * i <= n; i += 2)
    {
      if(n % i == 0)
        return false;
    }

    return true;
  }
}