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();
        System.out.format(“Answer = %s\n”, e.Problem());
    }
    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)
                P1.add(i);
        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)
                    P2.add(i);
            }
        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();
        System.out.format(“Answer = %s\n”, e.Problem());
    }
    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)
                P1.add(i);
        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)
                    P2.add(i);
            }
        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);
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s