1.

package sem2.am.circular;

/**
* Angewandte Mathematik, SS11
* Problem: 967 - Circular
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=11&page=show_problem&problem=908
*
* @author Florian Stein
* @author Franz Sommer
* @version 1.0, 04/10/2011
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 2.276
*/

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

class Main {

public static void main(String[] args) throws Exception {

// array enthaelt alle circular primes
int[] tmp = new int[] { 113, 131, 197, 199, 311, 337, 373, 719, 733,
919, 971, 991, 1193, 1931, 3119, 3779, 7793, 7937, 9311, 9377,
11939, 19391, 19937, 37199, 39119, 71993, 91193, 93719, 93911,
99371, 193939, 199933, 319993, 331999, 391939, 393919, 919393,
933199, 939193, 939391, 993319, 999331 };

// input reader
BufferedReader reader = new BufferedReader(new InputStreamReader(
System.in));

// string der zeile
String inputLine;

// variablen
int rootnumber = 0;
int limit = 0;
int found = 0;

// schleife
while (rootnumber != 1 && limit != 1) {

// exception von tokenizer abfangen falls -1
try {
inputLine = reader.readLine();
StringTokenizer token = new StringTokenizer(inputLine);
rootnumber = new Integer(token.nextToken());
limit = new Integer(token.nextToken());

found = 0;

// geht das array durch und zaehlt alle circs in der range
for (int i = 0; i < tmp.length; i++) {
if (tmp[i] >= rootnumber && limit >= tmp[i])
found++;
}

// ausgabe
if (found == 0)
System.out.println("No Circular Primes.");
if (found == 1)
System.out.println("1 Circular Prime.");
if (found > 1)
System.out.println(found + " Circular Primes.");
} catch (Exception e) {
rootnumber = 1;
limit = 1;
}
}
}
}

2.

/**
* Angewandte Mathematik, SS11
* Problem: 967- Circular
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=11&page=show_problem&problem=908
*
* @author Benjamin Vogt
* @author Sebastian Stumpf
* @version 1.0, 11/04/2011
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 2.112
*/

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main
{
public static void main(String[] args) throws IOException
{

int numberStart;
int numberEnd;
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
numberStart = Integer.valueOf(tokenizer.nextToken());
numberEnd = Integer.valueOf(tokenizer.nextToken());
int counter = 0;
try
{
while(numberStart != 1 && numberStart>=100 && numberEnd<= 1000000)
{
int [] circularPrimeArr = new int []{113, 131, 197, 199, 311, 337, 373, 719, 733, 919, 971, 991, 1193, 1931, 3119, 3779, 7793, 7937, 9311, 9377, 11939, 19391, 19937, 37199, 39119, 71993, 91193, 93719, 93911, 99371, 193939, 199933, 319993, 331999, 391939, 393919, 919393, 933199, 939193, 939391, 993319, 999331};

for (int i = 0; i < circularPrimeArr.length;i++)
{
if(numberStart<=circularPrimeArr[i] && numberEnd>=circularPrimeArr[i])
{

counter++;
}
}
System.out.println((counter == 0)? "No Circular Primes." :((counter==1)?"1 Circular Prime.": counter+" Circular Primes."));
counter=0;
tokenizer = new StringTokenizer(reader.readLine());
numberStart = Integer.valueOf(tokenizer.nextToken());
numberEnd = Integer.valueOf(tokenizer.nextToken());
}
}
catch(Exception e)
{
numberStart=1;
}
}
}

------------------------------------------

1.

package problemSetVolumes.volume009;

import java.util.ArrayList;
import java.util.Arrays;

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS10
* Problem: 967 - Circular
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=11&page=show_problem&problem=908
*
* @author Siegfried Ippisch
* @author Martin Lambeck
* @version 1.0
*
* Method : Sieve of Eratosthenes
* Status : Accepted
* Runtime: 2.128
*/
public class Circular {


static final int MAX = 1000001;
static final int SQRT_MAX = 1001;

public static boolean[] p = new boolean[MAX];

static ArrayList<Integer> cps = new ArrayList<Integer>(50);

public static void init()
{
Arrays.fill(p, true);
p[0] = false;
p[1] = false;

for (int i = 2; i <= SQRT_MAX; i++)
{
if (!p[i])
continue;

int sq_i = i*i;


for (int j = sq_i; j < MAX; j += i)
{
p[j] = false;
}
}

// for (int i = 19900; i <= 19999; i++)
// {
// if (p[i])
// System.out.println(i);
// }
}

public static void init2()
{
for (int i = 100; i < MAX; i++)
{
if (isCircPrime(i))
cps.add(i);
}
}

private static boolean isCircPrime(int z)
{
int left, mod;
int digits = (int) (Math.log10(z) + 0.0000001 + 1.0);

int pot10 = (int) (Math.pow(10, digits-1) + 0.0000001);

for (int i = 0; i < digits; i++)
{
if (!p[z])
return false;

left = z / pot10;
mod = z % pot10;

z = mod * 10;
z += left;
}

return true;
}

public static void main(String[] args) throws Exception
{
init();
init2();

BufferedIntReader in = new BufferedIntReader();

int a, b;

while((a = in.nextInt()) != 1)
{
b = in.nextInt();

int count = 0;

for (Integer x : cps)
{
if (x >= a && x <= b)
count++;
}

if (count == 0)
System.out.println("No Circular Primes.");
else if (count == 1)
System.out.println("1 Circular Prime.");
else
System.out.println(count + " Circular Primes.");
}

}

}

//reads int from stdin
class BufferedIntReaderX
{
byte[] buf = new byte[1024*32];
int pos = 0;
int len = 0;

public int nextInt() throws Exception
{
int num = 0;
int chr;
boolean found = false;

while (true)
{
if (pos == len)
{
pos = 0;
len = System.in.read(buf);
}

if (len == -1)
{
found = true;
chr = -1;

} else
{
chr = buf[pos];
pos++;
}

if (chr >= '0' && chr <= '9')
{
num = num*10 + (chr - '0');
found = true;

} else
{
if (found)
return num;
}
}
}
}


2.


package problemSetVolumes.volume009;

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS10
* Problem: 967 - Circular
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=11&page=show_problem&problem=908
*
* @author Siegfried Ippisch
* @author Martin Lambeck
* @version 1.0
*
* Method : Sieve of Eratosthenes
* Status : Accepted
* Runtime: 1.784
*/
public class Circular2 {

public static void main(String[] args) throws Exception
{
int[] pre = new int[] {113, 131, 197, 199, 311, 337, 373, 719, 733, 919, 971, 991, 1193, 1931, 3119, 3779, 7793, 7937, 9311, 9377, 11939, 19391, 19937, 37199, 39119, 71993, 91193, 93719, 93911, 99371, 193939, 199933, 319993, 331999, 391939, 393919, 919393, 933199, 939193, 939391, 993319, 999331};

BufferedIntReader in = new BufferedIntReader();

int a, b;

while((a = in.nextInt()) != 1)
{
b = in.nextInt();

int count = 0;

for (Integer x : pre)
{
if (x >= a && x <= b)
count++;
}

if (count == 0)
System.out.println("No Circular Primes.");
else if (count == 1)
System.out.println("1 Circular Prime.");
else
System.out.println(count + " Circular Primes.");
}

}

}

//reads int from stdin
class BufferedIntReader
{
byte[] buf = new byte[1024*32];
int pos = 0;
int len = 0;

public int nextInt() throws Exception
{
int num = 0;
int chr;
boolean found = false;

while (true)
{
if (pos == len)
{
pos = 0;
len = System.in.read(buf);
}

if (len == -1)
{
found = true;
chr = -1;

} else
{
chr = buf[pos];
pos++;
}

if (chr >= '0' && chr <= '9')
{
num = num*10 + (chr - '0');
found = true;

} else
{
if (found)
return num;
}
}
}
}



3.

/**
* 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.");
}

}
}

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