fork download
copy 
  1. #include<iostream>
  2. using namespace std;
  3.  
  4. const int N = int(1e6)+10;
  5. long long int Phi[N];
  6. bool prime[N];
  7.  
  8. void buildSieve()
  9. {
  10.     for(int i=0;i<N;i++)
  11.         Phi[i]=i,prime[i]=true;
  12.  
  13.     for(int i=2;i<N;i++)
  14.     {
  15.         if(prime[i]==false)
  16.             continue;
  17.  
  18.         for(int j=2*i;j<N;j+=i)
  19.         {
  20.             prime[j]=false;
  21.             Phi[j]/=i;
  22.             Phi[j]*=(i-1);
  23.         }
  24.     }
  25.     for(int i=2;i<N;i++)
  26.         if(prime[i]==true)
  27.             Phi[i]-=1;
  28. }
  29.  
  30. int main()
  31. {
  32.     buildSieve();
  33.     int n;
  34.     cin>>n;
  35.     long long int sum=0;
  36.  
  37.     for(int i=1;i<=n;i++)
  38.     {
  39.         sum+=Phi[i];
  40.     }
  41.     cout<<sum<<endl;
  42.  
  43. }
Runtime error #stdin #stdout 0.04s 12256KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/9VLKOn
language:
C++ (gcc 8.3)
created:
7 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!