====== GCD(n, k) = 1 ======

===== 풀이 =====
  * 오일러 피 함수값을 계산하는 문제. [[ps:곱셈적 함수#오일러 피 함수]] 참고.
  * 소인수분해를 이용해서 O(sqrt(n))에 계산 가능하다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 11689. GCD(n, k) = 1".

- Problem link: https://www.acmicpc.net/problem/11689
- Solution link: http://www.teferi.net/ps/problems/boj/11689

Tags: [Number theory]
"""

from teflib import numtheory


def euler_phi(n):
    for p in numtheory.prime_factorization_small(n):
        n -= n // p
    return n


def main():
    n = int(input())
    print(euler_phi(n))


if __name__ == '__main__':
    main()
</dkpr>
  * Dependency: [[:ps:teflib:numtheory#prime_factorization_small|teflib.numtheory.prime_factorization_small]]

{{tag>BOJ ps:problems:boj:골드_1}}