[BOJ/PYTHON] 11689. GCD(n, k) = 1

백준 문제 링크: https://www.acmicpc.net/problem/11689

문제 요약

자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하기

핵심 아이디어

오일러 피 함수를 쓰면 된다. 오일러 피 함수란 n이하의 서로소 개수를 구할 때 사용하는 함수이다.

n을 구성하는 소인수인 p들에 대해, n에 (1 - 1/p)를 곱하면 된다.

60의 경우 소인수분해하면 2^235라서, 2, 3, 5가 p이다. 오일러피 함수를 이용해 60 이하의 이하의 서로소 개수를 구하면, 60 * 1/2 * 2/3 * 4/5 = 16이다.

풀이

# gold1-11689. GCD(n, k) = 1

import sys, math
input = sys.stdin.readline

n = int(input())
answer = n

# 2부터 n의 제곱근까지의 모든 수 확인
for i in range(2, int(math.sqrt(n)) + 1):
    if n % i == 0:
        # n에서 i를 나눌 수 있는 만큼 나눠줌
        while n % i == 0:
            n //= i
        # 오일러 피 함수: (1 - 1/i)
        answer = answer * (1 - 1/i)

# 자기 자신이 소수임 
if n > 1:
    answer = answer * (1 - 1/n)

print(int(answer))

실행 시간

메모리 33508KB, 시간 156ms (python3)