fork download
copy 
  1. #include <stdio.h>
  2. #define MAX 1000000
  3. long long primes[MAX+1];
  4. char used[MAX+1];
  5. int main()
  6. {
  7.     int t,k,temp;
  8.     long long l,r,i,j,co;
  9.  
  10.     for(i=2;i*i<=MAX;i++)
  11.      if(!primes[i])
  12.        for(j=i*i;j<=MAX;j+=i)
  13.         primes[j]=1;
  14.  
  15.     for(j=0,i=2;i<=MAX;i++)
  16.       if(!primes[i])
  17.         primes[j++]=i;
  18.  
  19.     primes[j]=((long long)MAX+1);
  20.     scanf("%d",&t);
  21.     while(t--)
  22.     {
  23.         scanf("%lld%lld",&l,&r);
  24.  
  25.         if(l==1)
  26.           co=1;
  27.         else
  28.           co=0;
  29.  
  30.         for(i=0;i<=r-l;i++)
  31.           used[i]=0;
  32.  
  33.         for(i=0;primes[i]*primes[i]<=r;i++)
  34.            for(j=primes[i]*primes[i];j<=r;j+=primes[i])
  35.             if(j>=l && !used[j-l])
  36.             {
  37.               co++;
  38.               used[j-l]=1;
  39.             }
  40.         co=r-l+1-co;
  41.  
  42.         for(i=0;primes[i]*primes[i]<=r;i++)
  43.            for(temp=2,k=1,j=primes[i]*primes[i];j<=r;j*=primes[i],temp++)
  44.            {
  45.              if(j>=l && temp == primes[k]-1)
  46.              {
  47.                co++;
  48.                k++;
  49.              }
  50.            }
  51.  
  52.        printf("%lld\n",co);
  53.     }
  54.     return 0;
  55. }
Success #stdin #stdout 0.06s 11088KB
comments (?)
stdin
copy 
3
1 1000000
1000000 2000000
10 100
stdout
copy 
78687
70490
23
https://ideone.com/nNJIpj
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!