fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. typedef long long ll;
  7.  
  8. int lp[100000001], phi[100000001], pr[5761455];
  9. char pow[100000001];
  10.  
  11. int main() {
  12.   ios::sync_with_stdio(false);
  13.   cin.tie(0);
  14.   int sz = 0;
  15.   int n;
  16.   cin >> n;
  17.   for (int i = 2; i <= n; i++) {
  18.     if (!lp[i]) lp[i] = i, pr[sz++] = i, phi[i] = i - 1, pow[i] = 1;
  19.     for (int j = 0; j < sz && pr[j] <= lp[i] && pr[j] * i <= n; j++) {
  20.       int val = pr[j] * i;
  21.       lp[val] = pr[j];
  22.       if (pr[j] == lp[i]) {
  23.         pow[val] = pow[i] + 1;
  24.         int x = lp[val];
  25.         for (int j = 1; j < pow[val]; j++)
  26.           x *= lp[val];
  27.         if (x == val)
  28.           phi[val] = (x / lp[val]) * (lp[val] - 1);
  29.         else
  30.           phi[val] = phi[x] * phi[val / x];
  31.       }
  32.       else {
  33.         pow[val] = 1;
  34.         phi[val] = phi[i] * (pr[j] - 1);
  35.       }
  36.     }
  37.   }
  38.   phi[1] = 1;
  39.   int k = 0;
  40.   while (true) {
  41.     if (k >= n) break;
  42.     long long sum = 0;
  43.     for (int i = k + 1; i <= min(n, k + 100); i++)
  44.       sum += phi[i];
  45.     //cout << sum << ' ';
  46.     k += 100;
  47.   }
  48.   return 0;
  49. }
  50.  
Success #stdin #stdout 1.63s 904660KB
comments (?)
stdin
copy 
100000000
stdout
copy 
Standard output is empty
https://ideone.com/F6PwgN
language:
C++ (gcc 8.3)
created:
3 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!