10539 - Almost Prime Numbers

#include <stdio.h>
#include <math.h>

#define M 1000005
#define MH M/2
char prm[M/16+10];
long int prime[M];

void seive();
int isPrime(int);

int main()
{
    int t,i,j=0,s,lc,hc;
    long long l,h;
    //freopen("in.txt","r",stdin);
    scanf("%d",&t);
    seive();
    for(i=1;i<M;i++)
        if(isPrime(i))
            prime[j++]=i;

    while(t--)
    {
        scanf("%lld %lld",&l,&h);
        s=sqrt(l),lc=0,l=l-1;
        for(i=0;prime[i]<=s;i++)
            lc+=log(l)/log(prime[i])-1;

        s=sqrt(h),hc=0;
        for(i=0;prime[i]<=s;i++)
            hc+=log(h)/log(prime[i])-1;

        printf("%d\n",hc-lc);   
    }
    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 ( !(prm[n>>4]&(1<<( (n>>1)&0x7))) ) return 1;
    return 0;
}