목차

서로소

ps
링크acmicpc.net/…
출처BOJ
문제 번호4355
문제명서로소
레벨골드 1
분류

정수론

시간복잡도O(t * sqrt(n))
인풋사이즈t<=?, n<=10^9
사용한 언어Python 3.11
제출기록31256KB / 40ms
최고기록40ms
해결날짜2023/02/07

풀이

코드

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