fork(1) download 
  1. #include <cstdio>
  2. #include <cstring>
  3. #define maxab 1000003
  4. #define maxlv 13
  5. using namespace std;
  6. bool isPrime[maxab];
  7. int sumP[maxab],lv[maxab],c[maxab][maxlv];
  8. int getlv(int i){
  9.     if ((lv[i]>0)||(i<=1)) return lv[i];
  10.     else {
  11.         lv[i]=getlv(sumP[i])+1;
  12.         return lv[i];
  13.     }
  14. }
  15. void init(){
  16.     memset(isPrime,true,sizeof(isPrime));
  17.     memset(lv,0,sizeof(lv));
  18.     int i,j;    isPrime[0]=false;   isPrime[1]=false;
  19.     for (int i=2;i<maxab;i++) if (isPrime[i]==true){
  20.         sumP[i]=i;
  21.         lv[i]=1;
  22.         for (j=2;(i*j)<=maxab;j++){
  23.             isPrime[i*j]=false;
  24.             sumP[i*j]+=i;
  25.         }
  26.     }
  27.     for (i=2;i<maxab;i++) getlv(i);
  28.     for (i=0;i<=1;i++) for (j=0;j<maxlv;j++) c[i][j]=0;
  29.     for (i=2;i<maxab;i++){
  30.         for (j=0;j<maxlv;j++) c[i][j]=c[i-1][j];
  31.         c[i][lv[i]]++;
  32.     }
  33. }
  34. int main(){
  35.     init();
  36.     int ntest,test,a,b,k;
  37.     scanf("%d",&ntest);
  38.     for (test=1;test<=ntest;test++){
  39.         scanf("%d%d%d",&a,&b,&k);
  40.         if (k>=maxlv) printf("0");
  41.         else{
  42.             printf("%d",c[b][k]-c[a-1][k]);
  43.         }
  44.         if (test<ntest) printf("\n");
  45.     }
  46.     return 0;
  47. }
  48.  
Success #stdin #stdout 0.12s 62872KB
comments ()
stdin 
1
90 90 3
stdout 
1
https://ideone.com/Lmdgqj
language:
C++ (gcc 8.3)
created:
11 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!