<백준> 11689

GCD(n,k) = 1

문제
자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 자연수 n (1 ≤ n ≤ 1012)이 주어진다.

출력
GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 출력한다.

두 수의 최대공약수가 1인 수의 갯수를 구하는 것이다.

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	long long n;
	cin >> n;

	long long result = n;

	for (long i = 2; i * i <= n; i++)
	{
		if (n % i == 0)
		{
			result = result - (result / i);
			while (n % i == 0)
				n /= i;
		}
	}

	if (n > 1)
	{
		result = result - (result / n);
	}
	cout << result;
}