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], pre[100000001], pr[5761455];
  9.  
  10. int main() {
  11.   ios::sync_with_stdio(false);
  12.   cin.tie(0);
  13.   int n;
  14.   cin >> n;
  15.   int sz = 0;
  16.   for (int i = 2; i <= n; i++) {
  17.     if (!lp[i]) lp[i] = i, pr[sz++] = i, pre[i] = 1;
  18.     for (int j = 0; j < sz && pr[j] * i <= n && pr[j] <= lp[i]; j++) {
  19.       int val = pr[j] * i;
  20.       lp[val] = pr[j];
  21.       if (pr[j] == lp[i]) 
  22.         pre[val] = pre[i];
  23.       else
  24.         pre[val] = i;
  25.     }
  26.   }
  27.   lp[1] = 1;
  28.   for (int i = 2; i <= n; i++) {
  29.     if (pre[i] == 1)
  30.       lp[i] = (i / lp[i]) * (lp[i] - 1);
  31.     else
  32.       lp[i] = lp[i / pre[i]] * lp[pre[i]];
  33.   }
  34.   int k = 0;
  35.   while (true) {
  36.     if (k >= n) break;
  37.     ll sum = 0;
  38.     for (int i = k + 1; i <= min(n, k + 100); i++)
  39.       sum += lp[i];
  40.     cout << sum << ' ';
  41.     k += 100;
  42.   }
  43.   return 0;
  44. }
  45.  
Success #stdin #stdout 2.19s 807124KB
comments (?)
stdin
copy 
100000000
stdout
copy 
Standard output is empty
https://ideone.com/MlQO86
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!