10200 - Prime Time

#include <stdio.h>
#include <math.h>
#define eps 1e-6
#define M 5000000
#define MH M/2

int countEu[10001];
char prm[M/16+10];
int prime[M];

void seive();
int isPrime(int);
void count();

int main()
{
    register int a,b;
    double corr;

    //freopen("in.txt","r",stdin);
   
    seive();
    count();

    while(scanf("%d%d",&a,&b)==2)
    {
        corr=100.0*(countEu[b]-countEu[a-1])/(b-a+1)+eps;
        printf("%0.2lf\n",corr);
    }
    return 0;
}


void seive()
{
    int lim = (int)sqrt(M),i,j;
    for ( i = 3; i <= lim; i += 2){
        if ( !(prm[i>>4]&(1<<((i>>1)&0x7))) )
        {
            for (j = i*i/2; j <= MH; j+=i) prm[j>>3] |= (1<<(j&0x7));
        }
    }
}

int isPrime(int n)
{
    if ( n < 2) return 0;
    if ( n == 2) return 1;
    if ( n%2 == 0) return 0;

    if(n>=5000000)
    {
        for(int i=0;prime[i]<=sqrt(n);i++)
            if(n%prime[i]==0)
                return false;
            return true;
    }

    if ( !(prm[n>>4]&(1<<( (n>>1)&0x7))) ) return 1;
    return 0;
}

void count()
{
    int i,k=0;

    for(i=0;i<=M;i++)
        if(isPrime(i))
            prime[k++]=i;

    k=0;

    for(i=0;i<=10000;i++)
        if(isPrime(i*i+i+41))
            countEu[i]=++k;
        else
            countEu[i]=k;
}