A - Circular

Problem

A circular prime is a prime number that remains prime as each leftmost digit (most significant digit), in turn, is moved to the right hand side. For instance, the number 19937 is a circular prime, since all numbers in the sequence 19937, 99371, 93719, 37199 and 71993 are prime numbers. Your objective is to write a program that, given a range, computes the number of circular primes in that range.

Input

The input consists of a sequence of pairs of integers i and j, with one pair of integers per input line. All integers will be less than 1,000,000 and greater or equal to 100. You can assume that in any pair i is lesser or equal than j. You should process all pairs of integers, and for each such pair, count the number of circular primes between i and j, including i and j. Input is terminated by a line just with the number -1.

Output

For each pair of input integers, defining a range, the output should be: “No Circular Primes.” (if there are no circular primes in the range), “1 Circular Prime.” (if only one circular prime exists in the range), or “n Circular Primes.” (if there are n circular primes in the range, and n is greater than one).

Sample Input

1000 1100

100 120

100 1000

-1

Sample Output

No Circular Primes.

1 Circular Prime.

12 Circular Primes.

#include <stdio.h>
#include <string.h>
#include <math.h>

int DP[1000001] = {};
int Prime[5500], Pt;
void sieve() {
    Pt = 0;
    char mark[50000] = {};
    int i, j;
    for(i = 2; i < 50000; i++) {
        if(mark[i] == 0) {
            Prime[Pt++] = i;
            for(j = 2; i*j < 50000; j++)
                mark[i*j] = 1;
        }
    }
}
int judgePrime(int n) {
    static int i, sqr;
    sqr = (int)sqrt(n);
    for(i = 0; Prime[i] <= sqr && i < Pt; i++)
        if(n%Prime[i] == 0)
            return 0;
    return 1;
}
void build() {
    char str[20];
    int i, j, k, n, len, tmp;
    for(i = 100; i <= 1000000; i++) {
        DP[i] += DP[i-1];
        sprintf(str, "%d", i);
        len = strlen(str);
        for(j = 0; j < len; j++) {
            sscanf(str, "%d", &n);
            if(judgePrime(n) == 0)
                break;
            tmp = str[0];
            for(k = 1; k < len; k++)
                str[k-1] = str[k];
            str[len-1] = tmp;
        }
        if(j == len) {
            DP[i]++;
        }
    }
}
int main() {
    sieve();
    build();
    int a, b, sum;
    while(scanf("%d", &a) == 1 && a > 0) {
        scanf("%d", &b);
        sum = DP[b] - DP[a-1];
        if(sum == 0)
            puts("No Circular Primes.");
        else if(sum == 1) {
            puts("1 Circular Prime.");
        } else
            printf("%d Circular Primes.\n", sum);
    }
    return 0;
}