範例程式碼 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];
}