範例程式碼 uva10533

//uva10533
#include <stdio.h>
#define MAX 1000000

bool sieve[MAX];
int dp_acc[MAX] = {0};

int digit_sum(int n) {
	int sum = 0;
	for(; n > 0; n /= 10)
		sum += n % 10;
	return sum;
}

void init() {
	sieve[0] = sieve[1] = false;
	for(int i = 2; i < MAX; ++i)
		sieve[i] = true;
	for(int i = 2; i < MAX; i++)
		if(sieve[i])
			for(int j = i+i; j < MAX; j += i)
				sieve[j] = false;

	dp_acc[0] = dp_acc[1] = 0;
	for(int i = 2; i < MAX; ++i)
		dp_acc[i] = dp_acc[i - 1] + (sieve[i] && sieve[digit_sum(i)]);
}

int main() {
	int n, m1, m2;
	init();
	scanf("%d", &n);
	for(int loop = 0; loop < n; ++loop) {
		scanf("%d %d", &m1, &m2);
		printf("%d\n", dp_acc[m2] - dp_acc[m1 - 1]);
	}
	return 0;
}