1. 

/**
* FWP: Ausgewaehlte Probleme aus dem ACM (SS10)
*
* Method: Brute Force
* Problem: 967 - Circular
* Accepted: 1.828
* @author Evgeni Pavlidis
*
*/
import java.io.*;
import java.util.*;

class Main {

private static final int MAX = 1000000;
private static boolean[] isPrime = new boolean[MAX];
private static int[] isCircular = new int[MAX+1];
private static int[] circularNumbers = new int[MAX+1];


private static void sievePrimes()
{
for(int i = 3; i < MAX; i+=2)
isPrime[i] = true;

int root = (int)Math.sqrt(MAX);
for(int i = 3; i <= root; i+=2)
if(isPrime[i])
for(int j = i+i; j < MAX; j+=i)
isPrime[j] = false;
}

private static void checkPrimes()
{
int[] powers = new int[]{ 0, 1, 10, 100, 1000, 10000, 100000, 1000000 };
int[] save;
boolean circular;
int digit, check, c;

for(int p = 3; p <= 6; p++)
{
save = new int[p];

for(int i = powers[p]+1; i < powers[p+1]; i +=2)
if(isPrime[i] && isCircular[i] == 0)
{
circular = true;
c = 0;
check = i;

for(int j = 0; j < p; j++)
{
save[c++] = check;

check = check;
digit = check % 10;
check = check / 10 + powers[p]*digit;


//System.out.println(i + "(" + j + ") " + check);
if(!isPrime[check])
circular = false;
}

for(int j = 0; j < p; j++)
if(isCircular[save[j]] == 0)
isCircular[save[j]] = (circular)? 1 : -1;


}
}
}

private static void calcCirculars()
{
int sum = 0;
for(int i = 101; i <= MAX; i++)
if(isCircular[i] == 1)
circularNumbers[i] = ++sum;
else
circularNumbers[i] = sum;
}

public static void main(String...args) throws Exception
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int low, high, found;
String input;
StringBuffer output = new StringBuffer();
String[] in;

sievePrimes();
checkPrimes();
calcCirculars();

while( (input = reader.readLine().trim()) != null)
{
in = input.split(" ");
if(in.length == 1)
break;

low = Integer.parseInt(in[0]);
high = Integer.parseInt(in[1]);


found = circularNumbers[high] - circularNumbers[low-1];

output.append(((found == 0)? "No" : found) + " Circular Prime" + ((found==1)? ".\n":"s.\n"));
}

System.out.print(output);

}
}


************************************************************ Precalculated.java *********************

import java.io.*;
import java.util.*;

class Main {



private static final int MAX = 1000000;
private static boolean[] circular = new boolean[MAX+1];
private static int[] circularNumbers = new int[MAX+1];




private static void calcCirculars()
{
circular[113] = true;
circular[131] = true;
circular[197] = true;
circular[199] = true;
circular[311] = true;
circular[337] = true;
circular[373] = true;
circular[719] = true;
circular[733] = true;
circular[919] = true;
circular[971] = true;
circular[991] = true;
circular[1193] = true;
circular[1931] = true;
circular[3119] = true;
circular[3779] = true;
circular[7793] = true;
circular[7937] = true;
circular[9311] = true;
circular[9377] = true;
circular[11939] = true;
circular[19391] = true;
circular[19937] = true;
circular[37199] = true;
circular[39119] = true;
circular[71993] = true;
circular[91193] = true;
circular[93719] = true;
circular[93911] = true;
circular[99371] = true;
circular[193939] = true;
circular[199933] = true;
circular[319993] = true;
circular[331999] = true;
circular[391939] = true;
circular[393919] = true;
circular[919393] = true;
circular[933199] = true;
circular[939193] = true;
circular[939391] = true;
circular[993319] = true;
circular[999331] = true;

int sum = 0;
for(int i = 101; i <= MAX; i++)
if(circular[i])
circularNumbers[i] = ++sum;
else
circularNumbers[i] = sum;
}

public static void main(String...args) throws Exception
{
Scanner scanner = new Scanner(System.in);
int low, high, found;

calcCirculars();

while( scanner.hasNextInt() && (low = scanner.nextInt()) != -1 )
{
high = scanner.nextInt();

found = circularNumbers[high] - circularNumbers[low-1];

System.out.println(((found == 0)? "No" : found) + " Circular Primes.");
}



}
}


*************************************************************** Generator.java ***

import java.io.*;
import java.util.*;

class Main {



private static final int MAX = 1000000;
private static boolean[] isPrime = new boolean[MAX];
private static int[] isCircular = new int[MAX+1];
private static int[] circularNumbers = new int[MAX+1];


private static void sievePrimes()
{
for(int i = 3; i < MAX; i+=2)
isPrime[i] = true;

int root = (int)Math.sqrt(MAX);
for(int i = 3; i <= root; i+=2)
if(isPrime[i])
for(int j = i+i; j < MAX; j+=i)
isPrime[j] = false;
}

private static void checkPrimes()
{
int[] powers = new int[]{ 0, 1, 10, 100, 1000, 10000, 100000, 1000000 };
int[] save;
boolean circular;
int digit, check, c;

for(int p = 3; p <= 6; p++)
{
save = new int[p];

for(int i = powers[p]+1; i < powers[p+1]; i +=2)
if(isPrime[i] && isCircular[i] == 0)
{
circular = true;
c = 0;
check = i;

for(int j = 0; j < p; j++)
{
save[c++] = check;

check = check;
digit = check % 10;
check = check / 10 + powers[p]*digit;


//System.out.println(i + "(" + j + ") " + check);
if(!isPrime[check])
circular = false;
}

for(int j = 0; j < p; j++)
if(isCircular[save[j]] == 0)
isCircular[save[j]] = (circular)? 1 : -1;


}
}
}

private static void calcCirculars()
{
int sum = 0;
int last = 100;
for(int i = 101; i <= MAX; i++)
if(isCircular[i] == 1)
{

System.out.printf(" for(i = %d; i < %d; i++)\n" +
" circular[i] = %d;\n\n",
last, i, sum);
last = i;
circularNumbers[i] = ++sum;
}
else
circularNumbers[i] = sum;
}

public static void main(String...args) throws Exception
{
Scanner scanner = new Scanner(System.in);
int low, high, found;

sievePrimes();
checkPrimes();
calcCirculars();

while( (low = scanner.nextInt()) != -1 )
{
high = scanner.nextInt();

if(low == high)
found = circularNumbers[high];
else
found = circularNumbers[high] - circularNumbers[low];

System.out.println(((found == 0)? "No" : found) + " Circular Primes.");
}

}
}

*************************************************