fork(1) download
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int euler_f (int n) {
  6. int result = n;
  7. for (int i = 2; i * i <= n; ++i) {
  8. if (n % i == 0) {
  9. while (n % i == 0) n /= i;
  10. result -= result / i;
  11. }
  12. }
  13. if (n > 1) result -= result / n;
  14. return result;
  15. }
  16.  
  17. int main() {
  18. int n;
  19. cin >> n;
  20. int sum = 0;
  21. for (int i = 2; i <= n; ++i) {
  22. sum += euler_f(i);
  23. }
  24. cout << sum;
  25. return 0;
  26. }
Success #stdin #stdout 0s 4520KB
stdin
10000
stdout
30397485