fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #define P(X) printf("db %d\n",X);
  3. #define ll long long
  4. #define rep(i,n) for(i=1;i<=n;i++)
  5. using namespace std;
  6. int pr[79500];
  7. bool ar[1100005];
  8. void siv()
  9. {
  10. 	int N=1000000,in=0,i,j,sq;
  11.     sq=sqrt(N);
  12. 	for(i=4;i<=N;i+=2) ar[i]=1;
  13. 	for(i=3;i<=sq;i+=2){
  14. 		if(ar[i]==0)
  15. 		{
  16. 			for(j=i*i;j<=N;j+=i) ar[j]=1;
  17. 		}
  18. 	}
  19. 	ar[1]=1;
  20. 	for(i=1;i<N;i++){
  21.         if(!ar[i]){
  22.         in++;
  23.         pr[in]=i;
  24.         }
  25. 	}
  26. }
  27. int fn(ll x)
  28. {
  29.     int n=0,r=sqrt(x)+1,i,p;
  30.     for(i=1;pr[i]<=r;i++){
  31.         for(p=2;;p++){
  32.             if(pow(pr[i],p)>x)break;
  33.         }
  34.         n+=p-2;
  35.     }
  36.     return n;
  37. }
  38. int main()
  39. {
  40.     int i,ts;
  41.     ll a,b;
  42.     //freopen("test.in","r",stdin);
  43.     scanf("%d",&ts);
  44.     siv();
  45.     //P(fn(3))
  46.     while(ts--){
  47.         scanf("%lld %lld",&a,&b);
  48.         printf("%d\n",fn(b)-fn(a-1));
  49.     }
  50.     return 0;
  51. }
  52.  
  53.  
Success #stdin #stdout 0.01s 4528KB
comments (?)
stdin
copy 
3
1 5
1 20
20 60
stdout
copy 
1
4
4
https://ideone.com/mzmE6G
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!