[백준] 11689번 GCD(n, k) = 1 ★★★

💡문제접근

• 오일러 피 함수에 대한 공부

• 이 때, p는 소인수이다.

💡코드(메모리 : 31256KB, 시간 : 164ms)

import sys
input = sys.stdin.readline

N = int(input())
answer = N

for i in range(2, int(N**0.5)+1):
    if N % i == 0:
        while N % i == 0:
            N //= i
        answer -= answer // i

if N > 1:
    answer -= answer // N
print(answer)

💡소요시간 : 1h