fork download
copy 
  1. #include<iostream>
  2. #include<stdio.h>
  3. #define MAX_NUM 1000001 
  4. int primes[MAX_NUM];
  5. int nfactor[15][1000010];
  6.  
  7. void gen_sieve_primes(void)
  8. {
  9.     primes[2]=1;
  10.     for(int i=4;i<MAX_NUM;i+=2)
  11.         primes[i]++;
  12.  
  13.     for (int p=3; p<MAX_NUM; p+=2)
  14.     {
  15.         if(primes[p] == 0)
  16.         {
  17.             primes[p] = 1;
  18.             for(int j = 2*p;j<MAX_NUM;j+=p)
  19.                 primes[j]++;
  20.         }
  21.     }
  22.  
  23.     for(int i=1;i<MAX_NUM;i++)
  24.     {
  25.         for(int j=0;j<11;j++)
  26.         {
  27.  
  28.             if(primes[i]==j)
  29.             {
  30.                 nfactor[j][i]=nfactor[j][i-1]+1;
  31.             } 
  32.             else
  33.             {
  34.                 nfactor[j][i]=nfactor[j][i-1];
  35.             }
  36.  
  37.         }
  38.     }
  39. }
  40.  
  41. int main()
  42. {
  43.     gen_sieve_primes();
  44.  
  45.     int t,a,b, n, count=0;
  46.     scanf("%d",&t);
  47.  
  48.     while(t--)
  49.     {
  50.         count =0;
  51.         scanf("%d %d %d",&a,&b,&n);
  52.         printf("%d\n",nfactor[n][b]-nfactor[n][a-1]);
  53.     }
  54. }
Success #stdin #stdout 0.09s 65792KB
comments (?)
stdin
copy 
5
1 3 1
1 10 2
1 10 3
1 100 3
1 1000 0
stdout
copy 
2
2
0
8
1
https://ideone.com/a4dnzT
language:
C++ (gcc 8.3)
created:
10 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!