XTU OJ 1396

#include<stdio.h>
int num[1000007];
int a  [1000007];
const int p=1000001;
/*
2
1 2
1 1000000
*/
int main()
{
    for(int i=2;i<p/i;i++){
        if(!num[i]){
//            a[i]=1;
            for(int j=i*i;j<=p;j+=i) num[j]=1;//打上合数； 
        }
    }
    for(int i=2;i<=p;i++){
        if(!num[i]){
            a[i]=1;
            for(int j=1;j*i<=p;j++){
                a[j*i]=a[i]+a[j];
            }
        }
    }
    for(int i=1;i<=p;i++) a[i]+=a[i-1];    
    int k;
    scanf("%d",&k);
    while(k--)
    {
        int A,b;
        scanf("%d %d",&A,&b);
        printf("%dn",a[b]-a[A-1]);
    }
    return 0;
}