Euler's Totient Function

Euler’s Totient function Φ(n) for an input n is count of numbers in {1, 2, 3, …, n} that are relatively prime to n, i.e., the numbers whose GCD (Greatest Common Divisor) with n is 1.

Program:-

#include <bits/stdc++.h>
using namespace std;

int Euler(int n){
    int result = n;
    for(int i=2;i*i<=n;i++){
        if(n%i == 0){
            while(n%i == 0) n = n/i;
            result = result - result/i;
        }
    }
    if(n>1) result = result - result/n;
    return result;
}

int main() {
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cout<<"Euler Totient of ";
        cout<<i<<" = "<<Euler(i)<<endl;
    }
    return 0;
}