서로소

• 그냥 주어진 n에 대해서 오일러 피 함수를 계산해주기만 하면 되는 문제이다. GCD(n, k) = 1와 거의 동일하다. (GCD(a,b)==1 이라는 것과 a와 b가 서로소라는 것이 동치이니..). 코드도 거의 동일
• 그러나 딱 한가지 주의할점은, 'n보다 작은 양의 정수 중에서' 라는 조건이다. n=1일때에는 1이 아닌 0을 답으로 출력해줘야 한다.

"""Solution code for "BOJ 4355. 서로소".

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

Tags: [Math] [Number theory]
"""

import sys
from teflib import numtheory


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


def main():
    while (line := sys.stdin.readline().rstrip()) != '0':
        n = int(line)
        print('0' if n == 1 else euler_phi(n))


if __name__ == '__main__':
    main()

• Dependency: teflib.numtheory.prime_factorization_small