UVa 10533 - Digit Primes

// UVa 10533 - Digit Primes

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

#define LIMIT 1000000

int digit_prime_count_up_to[LIMIT + 1];
bool is_prime[LIMIT + 1];

void generate_primes() {
	memset(is_prime, true, sizeof(is_prime));
	is_prime[0] = false;
	is_prime[1] = false;
	for (int j = 4; j <= LIMIT; j += 2)
		is_prime[j] = false;
	for (int i = 3; i <= 1000; i++)
		if (is_prime[i]) {
			for (int j = i * i; j <= LIMIT; j += i)
				is_prime[j] = false;
		}
}

void generate_digit_prime_numbers() {
	digit_prime_count_up_to[0] = 0;
	digit_prime_count_up_to[1] = 0;
	for (int i = 2; i <= LIMIT; i++) {
		digit_prime_count_up_to[i] = digit_prime_count_up_to[i - 1];
		if (is_prime[i]) {
			int digit_sum = 0;
			for (int j = i; j; j /= 10) {
				digit_sum += j % 10;
			}
			if (is_prime[digit_sum])
				digit_prime_count_up_to[i]++;
		}
	}
}

int main() {
	generate_primes();
	generate_digit_prime_numbers();

	int cases;
	for (scanf("%d", &cases); cases; cases--) {
		int start, end;
		scanf("%d%d", &start, &end);
		printf("%d\n", digit_prime_count_up_to[end] - digit_prime_count_up_to[start - 1]);
	}
	return 0;
}