uva10539

 1 #include<cstdio>
 2 #include<cmath>
 3 #define LL long long
 4 const int maxn=1200010;
 5 int pri[maxn];
 6 int ispri[maxn];
 7 int cnt;
 8 void init()
 9 {
10     cnt=0;
11     int m=sqrt(maxn+0.5);
12     for(int i=2;i<=m;i++) if(!ispri[i])
13         for(int j=i*i;j<=maxn;j+=i)
14         ispri[j]=1;
15         for(int i=2;i<=maxn;i++)
16             if(!ispri[i]) pri[cnt++]=i;
17 
18 }
19 LL query(LL x)
20 {
21     LL ans=0;
22     for(int i=0;i<cnt&&(LL)pri[i]*pri[i]<=x;i++)
23     ans+=log(x+0.1)/log(pri[i])-1;
24     return ans;
25 }
26 int main()
27 {
28     int n;
29     init();
30     scanf("%d",&n);
31     {
32         while(n--)
33         {
34             LL l,r;
35             scanf("%lld%lldd",&l,&r);
36             printf("%lld
",query(r)-query(l-1));
37         }
38     }
39 }