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

1️⃣문제 설명

자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오.

2️⃣입력

첫째 줄에 자연수 n (1 ≤ n ≤ 1012)이 주어진다.

3️⃣출력

GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 출력한다.

 

---

👩🏻‍💻작성한 코드

import math

n = int(input())
answer = n

for i in range(2, int(math.sqrt(n) + 1)):
    if n % i == 0:  # i가 소인수인지 확인
        answer -= answer / i   # i의 배수 개수만큼 삭제
        while n % i == 0:   # i 거듭제곱 삭제
            n /= i

if n > 1:
    answer -= answer / n

print(int(answer))

💡코드 설명

이 문제는 소수를 구하는 문제이고 오일러 피 함수 개념을 사용해서 해결했다.

 

오일러 피 함수란?

1부터 N까지 범위에서 N과 서로소인 자연수의 개수이다.

for i in range(2, int(math.sqrt(n) + 1)):
    if n % i == 0:
        answer -= answer / i 
        while n % i == 0:
            n /= i

⬆️if 문을 통해 i가 소인수인지 확인한다. 

 

만약 소인수라면, answer에서 i의 배수의 개수만큼 빼준다.

 

그리고 while 문을 통해 i의 거듭제곱을 없애준다 -> 예를 들어 n = 3² *11 (=99)일 때, 3²를 없애고 11만 남김

if n > 1:
    answer -= answer / n

⬆️for문에서 소인수 값을 제곱근까지만 확인했으므로 소인수가 누락되는 경우를 처리한다. -> 위 예시를 이어서 보면 n = 11로 남았으므로, 11의 배수의 개수를 빼주는 과정