# Project Euler

### A Taste of Number Theory

#### 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;
}
}
```