fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. void computeTotient(int n, vector<int>& phi) {
  6.     // Initialize phi array
  7.     for (int i = 1; i <= n; i++) {
  8.         phi[i] = i;
  9.     }
  10.  
  11.     // Compute totient values using the modified Sieve of Eratosthenes
  12.     for (int i = 2; i <= n; i++) {
  13.         if (phi[i] == i) { // Check if i is prime
  14.             for (int j = i; j <= n; j += i) {
  15.                 phi[j] = phi[j] / i * (i - 1);
  16.             }
  17.         }
  18.     }
  19. }
  20.  
  21. int main() {
  22.     int n;
  23.     cout << "Enter the value of n: ";
  24.     cin >> n;
  25.  
  26.     vector<int> phi(n + 1);
  27.     computeTotient(n, phi);
  28.  
  29.     // Display the totient values
  30.     cout << "Euler's Totient Function values up to " << n << " are:\n";
  31.     for (int i = 1; i <= n; i++) {
  32.         cout << "phi(" << i << ") = " << phi[i] << "\n";
  33.     }
  34.  
  35.     return 0;
  36. }
Success #stdin #stdout 0s 5264KB
comments ()
stdin
copy 
12
stdout
copy 
Enter the value of n: Euler's Totient Function values up to 12 are:
phi(1) = 1
phi(2) = 1
phi(3) = 2
phi(4) = 2
phi(5) = 4
phi(6) = 2
phi(7) = 6
phi(8) = 4
phi(9) = 6
phi(10) = 4
phi(11) = 10
phi(12) = 4
https://ideone.com/5Dq6Qv
Euler's Totient
language:
C++ (gcc 8.3)
created:
121 days 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!