範例程式碼 uva967

//uva967
#include <cstdio>
#include <cmath>

const int n_max = 1000000;
bool not_primes[n_max + 1]; // not_primes[i] is true if i is not a prime
int nr_circular_primes[n_max + 1];
	// nr_circular_primes[i] is the number of circular primes up to i

void sieve_of_eratosthenes() {
	for(int i = 2, e = static_cast<int>(sqrt(static_cast<double>(n_max))); i <= e; i++)
		if(!not_primes[i])
			for(int j = i * i; j <= n_max; j += i)
				not_primes[j] = true;
}

int get_number(int length, int* digits) {
	int n = 0;
	for(int i = 0; i < length; i++, digits++) {
		if(i)
			n *= 10;
		n += *digits;
	}
	return n;
}

bool is_circular_prime(int n) {
	if(not_primes[n])
		return false;
	const int nr_digits_max = 8;
	int digits[nr_digits_max * 2];
	int length;
	for(length = 1; ; length++) {
		digits[nr_digits_max - length] = n % 10;
		n /= 10;
		if(!n)
			break;
	}
	for(int i = nr_digits_max - length, j = nr_digits_max, k = length - 1; k; k--) {
		digits[j++] = digits[i++];
		if(not_primes[get_number(length, &digits[i])])
			return false;
	}
	return true;
}

int main() {
	sieve_of_eratosthenes();
	int nr = 0;
	for(int n = 100; n <= n_max; n++) {
		if(is_circular_prime(n))
			nr++;
		nr_circular_primes[n] = nr;
	}
	while(true) {
		int i, j;
		scanf("%d", &i);
		if(i == -1)
			break;
		scanf("%d", &j);
		nr = nr_circular_primes[j] - nr_circular_primes[i - 1];
		if(!nr)
			puts("No Circular Primes.");
		else if(nr == 1)
			puts("1 Circular Prime.");
		else
			printf("%d Circular Primes.\n", nr);
	}
	return 0;
}