====== 서로소 ======

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

===== 코드 =====
<dkpr py>
"""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()
</dkpr>
  * Dependency: [[:ps:teflib:numtheory#prime_factorization_small|teflib.numtheory.prime_factorization_small]]

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