GCD(n, k) = 1

• 오일러 피 함수값을 계산하는 문제. 오일러 피 함수 참고.
• 소인수분해를 이용해서 O(sqrt(n))에 계산 가능하다.

"""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()

• Dependency: teflib.numtheory.prime_factorization_small