範例程式碼 uva10200

//uva10200
#include <stdio.h>
#include <string.h>
#define SIZE 10001
#define PRIMECNT 1229

int isPrime[SIZE], prime[PRIMECNT], primeCnt[SIZE];

void init();
int f(int);

int main() {
	init();
	int a, b;

	while (scanf("%d %d", &a, &b) != EOF)
		printf("%.2f\n", ((f(b) - f(a - 1)) * 100.00 / (b - (a - 1))) + 1e-9);

	return 0;
}

void init() {
	int i, j, index = 0;

	memset(isPrime, 0, sizeof(isPrime));

	for (i = 2; i < SIZE; i++) {
		if (isPrime[i] == 0) {
			prime[index++] = i;
			for (j = 2; i * j < SIZE; j++) {
				isPrime[i * j] = 1;
			}
		}
	}

    int num;
    primeCnt[0] = 1 - isPrime[41];
	for (i = 1; i < SIZE; i++) {
        num = i * i + i + 41;

        if (num < SIZE)
            primeCnt[i] =  primeCnt[i - 1] + (1 - isPrime[num]);
        else {
            for (j = PRIMECNT - 1; j >= 0 && num % prime[j]; j--) ;
            if (j < 0)
                primeCnt[i] =  primeCnt[i - 1] + 1;
            else
                primeCnt[i] =  primeCnt[i - 1];
        }
	}
}

int f(int n) {
    return primeCnt[n];
}