[백준] 11689번 : GCD(n, k) = 1 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

11689번: GCD(n, k) = 1

 

1. 문제 설명

2. 풀이과정

문제에서 요구하는 GCD(n, k) = 1을 만족하는 자연수의 개수가 오일러 피 함수의 정의이다.

해당 문제는 오일러 피 함수를 잘 구현할 수 있는지 물어보는 문제라고 할 수 있다.

 

오일러 피 함수 P[N]의 정의는 1부터 N까지 범위에서 N과 서로소인 자연수의 개수를 뜻한다.

오일러 피 함수의 원리를 살펴보면, 우선 구하고자 하는 오일러 범위만큼 리스트를 자기 자신의 인덱스 값으로 초기화한다. 이후 2부터 시작해 현재 리스트의 값과 인덱스가 같으면(= 소수) 현재 선택된 숫자(K)의 배수에 해당하는 수를 리스트에 끝까지 탐색하며 P[i] = P[i] - P[i] / K 연산을 수행한다.

위 과정을 리스트의 끝까지 반복한다.

 

서로소의 개수를 표현하는 변수 result를 따로 생성하고 현재 소인수 구성을 표현하는 변수 n을 입력받는다.

오일러 피 함수의 핵심을 참고해 2부터 n의 제곱근까지 탐색하며 해당 수가 소인수일 때 서로소의 개수를 result = result - result / 소인수 연산으로 result 값을 업데이트한다.

n에서 해당 소인수는 나누기 연산으로 삭제하여 이전 수의 배수들을 중복하지 않는다.

끝까지 탐색한 후, 현재 n이 1보다 크면 n이 마지막 소인수라는 뜻이므로 result = result - result / n 연산으로 result 값을 마지막으로 업데이트한다.

 

슈도코드

1. n(소인수 표현)
2. result(결괏값)
3. for 2 ~ n의 제곱근:
   1. if (현재 값이 소인수라면):
      1. 결괏값 = 결괏값 - 결괏값 / 현재 값
      2. n에서 현재 소인수 내역을 제거 (2*2*2*2*2*11*13 → 11*13으로 변경)
4. if (현재 n이 1보다 크면): 결괏값 = 결괏값 - 결괏값 / n
5. 결괏값 출력

반응형

3. 소스코드

import sys
import math

n = int(sys.stdin.readline())

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

if (n > 1):
    result = result - result / n
    
print(int(result))