## Project Euler Problem #37

### May 4, 2010

Read the details of the problem here

Summary

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

Solution

Straightforward to create a simple, though somewhat wordy, solution using maths functions to truncate the primes. I did consider using a string solution but thought that this version would be faster. I used a prime sieve and guessed at a suitable maximum, as performance with BigInteger().isProbablePrime() is poor.

```def LIMIT = 1000000
def isPrime = new boolean[LIMIT+1]
Arrays.fill(isPrime, true)
(0..1).each { isPrime[it] = false }

for (int i in 2..<Math.sqrt(LIMIT)) {
if (!isPrime[i]) continue
def j = i + i
while (j < LIMIT) {
isPrime[j] = false
j += i
}
}

def (answer, c) = [ 0, 0 ]

for (i in 11..<LIMIT) {
if (isPrime[i]) {
def n = i.intdiv(10)
while ((n > 0) && isPrime[n]) {
n = n.intdiv(10)
}
if (n > 0) continue
def m = 10 ** (int)Math.log10(i)
n = i % m
while ((n > 0) && isPrime[n]) {
m = m.intdiv(10)
n %= m
}
if (n == 0) {
if (++c == 11) break
}
}
}
```

This runs in 0.78 seconds. So fast enough for this solution. As a matter of interest I also created a string-based version (code as below, making use of the same sieve routine as above) and this ran in 1.21 seconds. An iterative solution still using strings would probably be faster as it could shortcut when the criteria wasn’t met.

```def (answer, c) = [ 0, 0 ]

for (i in 11..<LIMIT) {

if (!isPrime[i]) continue

def s = i.toString()

if ((0..<s.size()-1).collect { s[0..it].toInteger() }.every { isPrime[it] } &&
(1..<s.size()).collect { s[it..-1].toInteger() }.every { isPrime[it] }) {