fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. set< long long int > primes;
  6. int fac[5000003];
  7. void sieve(long long int n)
  8. {
  9.     long long int i,j,k;
  10.     n=n/2;
  11.     bool *b=(bool*)malloc(n*sizeof(bool));
  12.     primes.insert(2);
  13.     fac[2]=1;
  14.     for(i=0;i<n;i++)
  15.     {
  16.         b[i]=true;
  17.     }
  18.     for(i=0;i<n;i++)
  19.     {
  20.         if(b[i]==true)
  21.         {
  22.             k=2*i+3;
  23.             primes.insert(k);
  24.             fac[k]=1;
  25.             for(j=2*i*i+6*i+3;j<n;j+=k)
  26.             {
  27.                 b[j]=false;
  28.             }
  29.         }
  30.     }
  31.  
  32.     free(b);
  33.     return;
  34. }
  35.  
  36. int cal(int n)
  37. {
  38.     if(fac[n]!=0)
  39.     return fac[n];
  40.     else
  41.     {
  42.         set< long long int >::iterator it=primes.begin();
  43.         while(n%(*it)!=0)
  44.         {
  45.             it++;
  46.         }
  47.         return 1+fac[n/(*it)];
  48.     }
  49. }
  50. int main()
  51. {
  52.     int t,n,i,j,k,l;
  53.     cout << 1 << fac[3678] << " " << fac[3236] << endl;
  54.     for(i=1;i<=5000000;i++)
  55.     {
  56.         fac[i]=0;
  57.     }
  58.     sieve(5000000);
  59.     cout << 3;
  60.     for(i=1;i<=5000000;i++)
  61.     {
  62.         fac[i]=cal(i);
  63.     }
  64.     cin >> t;
  65.     cout << 1;
  66.     while(t--)
  67.     {
  68.         cin >> j >> k;l=0;
  69.         for(i=k+1;i<=j;i++)
  70.         l+=fac[i];
  71.         cout << l;
  72.     }
  73.     return 0;
  74. }
  75.  
Time limit exceeded #stdin #stdout 5s 33768KB
comments (?)
stdin 
2
3 1
6 3
stdout 
10 0
https://ideone.com/XArvT9
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
secret

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!