#include <iostream>
using namespace std;
int phi(int n) {
int result = n; // Initialize result as n
// Consider all prime factors of n and subtract their multiples from result
for (int p = 2; p * p <= n; ++p) {
if (n % p == 0) {
while (n % p == 0)
n /= p;
result -= result / p;
}
}
// If n has a prime factor greater than sqrt(n), subtract its multiple
if (n > 1)
result -= result / n;
return result;
}
int main() {
int n;
cout << "Enter a number: ";
cin >> n;
int result = phi(n);
cout << "Phi(" << n << ") = " << result << endl;
return 0;
}