서로소

 

#include <iostream>
 
using namespace std;
 
typedef long long ll;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    ll n;
    while (1) {
        cin >> n;
 
        if (!n) break;
 
        //소인수분해한다. 
 
        ll tmp = n;
        ll res = n;
        for (ll i = 2; i*i <= tmp; i++)
        {
            if (n % i == 0) {
                while ((n%i) == 0) {
                    //나눠질때까지 나눈다. (이 수의 배수들도 모두 서로소가 아니기 때문에)
                    n /= i;
                }
                res -= res / i;
            
            }
        }
        if (n > 1) res -= res / n;
        cout << res << '\n';
    }
 
    return 0;
}