Euler Problem 35

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?

This one was pretty easy, but parts of the program aren’t optimized. Just generate all the primes under one million, then test for circular prime. Generating the primes is easy and the fast part (as per previous problems). But I couldn’t work out an efficient routine for the testing. This one took about 5 minutes to run.

import java.util.*;

public class Euler35
{
    public static void main(String[] args)
    {
        System.out.format(“Problem 35:\n”);
        Euler35 e = new Euler35();
        System.out.format(“Answer = %s\n”, e.Problem());
    }
    public String Problem ()
    {
        ArrayList<Integer> P = new ArrayList<Integer>();
        ArrayList<Integer> C = new ArrayList<Integer>();
        ArrayList<Integer> g = new ArrayList<Integer>();
        String s = “”;
        boolean flag = true;
        int i2 = 0;
        int n = 1000000;
        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)
                P.add(i);
        for (int i: P)
        {
            s = String.valueOf(i);
            g.clear();
            g.add(i);
            flag = true;
            for (int j = 1; j <= s.length()-1; j++)
            {
                i2 = Integer.valueOf(s.substring(j) + s.substring(0, j));
                if (P.contains(i2) && flag)
                    g.add(i2);
                else
                    flag = false;
            }
            if (flag)
                for (int m: g)
                    if (C.contains(m) == false)
                        C.add(m);
        }
        return String.valueOf(C.size());
    }
}