# Euler 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.

﻿Got it, but its not pretty. This one almost amounts to brute force, although I figured out to split the right-to-left first, to reduce the pool before doing the left-to-right. This cut the time down in half to 4 mins on a loaded system.

import java.util.*;

public class Euler37
{
public static void main(String[] args)
{
System.out.format(“Problem 37:\n”);
Euler37 e = new Euler37();
}
public String Problem ()
{
ArrayList<Integer> P1 = new ArrayList<Integer>();
ArrayList<Integer> P2 = new ArrayList<Integer>();
String l2r = “”, r2l = “”;
boolean flag = true;
int n = 1000000, sum = 0;
boolean [] isPrime = new boolean [n+1];
for (int i = 2; i < n; i++)
isPrime[i] = true;
for (int p = 2; p*p < n; p++)
if (isPrime[p] == true)
for (int m = p*p; m < n; m = m+p)
if (m % p == 0)
isPrime[m] = false;
for (int i = 2; i < n; i++)
if (isPrime[i] == true)
for (int i : P1)
if (i >= 11)
{
l2r = Integer.toString(i);
flag = true;
for (int m = 0; m <= l2r.length()-1; m++)
if (P1.contains(Integer.valueOf(l2r.substring(m))) == false)
flag = false;
if (flag)
}
for (int i : P2)
{
r2l = Integer.toString(i);
flag = true;
for (int m = 0; m <= r2l.length()-1; m++)
if (P1.contains(Integer.valueOf(r2l.substring(0,r2l.length()-m))) == false)
flag = false;
if (flag)
{
System.out.format(“%d\n”,i);
sum += i;
}
}
return String.valueOf(sum);
}
}

package euler;

import java.util.*;
//import java.math.*;

public class Euler37
{
public static void main(String[] args)
{
System.out.format(“Problem 37:\n”);
Euler37 e = new Euler37();
}
public String Problem ()
{
ArrayList<Integer> P1 = new ArrayList<Integer>();
ArrayList<Integer> P2 = new ArrayList<Integer>();
String l2r = “”, r2l = “”;
boolean flag = true;
int n = 1000000, sum = 0;
boolean [] isPrime = new boolean [n+1];
for (int i = 2; i < n; i++)
isPrime[i] = true;
for (int p = 2; p*p < n; p++)
if (isPrime[p] == true)
for (int m = p*p; m < n; m = m+p)
if (m % p == 0)
isPrime[m] = false;
for (int i = 2; i < n; i++)
if (isPrime[i] == true)
for (int i : P1)
if (i >= 11)
{
l2r = Integer.toString(i);
flag = true;
for (int m = 0; m <= l2r.length()-1; m++)
if (P1.contains(Integer.valueOf(l2r.substring(m))) == false)
flag = false;
if (flag)
}
for (int i : P2)
{
r2l = Integer.toString(i);
flag = true;
for (int m = 0; m <= r2l.length()-1; m++)
if (P1.contains(Integer.valueOf(r2l.substring(0,r2l.length()-m))) == false)
flag = false;
if (flag)
{
System.out.format(“%d\n”,i);
sum += i;
}
}
return String.valueOf(sum);
}
}