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