Q10200: Prime Time

// Run time: 0.080
#include <stdio.h>
#include <math.h>
#define EPS pow(10, -9)  // 誤差用
#define N 10007
int prime[1230];
int arr[N];
bool isprime[N+1];
bool state[N+1];
int calculate(int n);
bool test(int n);

int main()
{
    int i, j;

    // 找2到超過10000的質數
    for ( i = 2; i <= N; i++)
        if (!isprime[i])
            for ( j = 2*i; j <= N; j+=i)
                isprime[j] = true;

    // assign prime to array
    for ( i = 2, j = 0; i <= N; i++)
        if (!isprime[i])
            prime[j++] = i;

    int a, b;
    int n;
    int cnt = 0;
    double percent;


    for ( i = 0; i <= 10000; i++)
    {
        n = calculate(i);
        arr[i] = test(n) ? ++cnt : cnt;
    }

    while (scanf("%d%d", &a, &b) == 2)
    {
        if (a >= 1 && arr[a] == arr[a-1])
            percent = ((arr[b]-arr[a])*100+EPS)/(b-a+1);
        else
            percent = ((arr[b]-arr[a]+1)*100+EPS)/(b-a+1);
        printf("%.2lf\n", percent);
    }

    return 0;

}

int calculate(int n)
{
    return n * n + n + 41;
}

bool test(int n)
{
    int i;
    for ( i = 0; prime[i]*prime[i] <= n; i++)
        if (!(n%prime[i]))
            return false;

    return true;
}