[백준 11689번] 파이썬 - GCD(n, k) = 1

백준 11689 - GCD(n, k) = 1

시간제한 1초, 메모리 제한 256MB

# 조건

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

입력

• 첫째 줄에 자연수 n (1 ≤ n ≤ 10^12)이 주어진다.

출력

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

# 접근 방법

• n이 주어졌을 때 서로소인 수의 갯수를 구하는 문제이다.
• 관련된 공식이 있을 것 같아 검색해보니 오일러 피(파이) 함수라는 것이 존재하였다.
  • 아래 식과 같이 구할 수 있으며 핵심 성질은
  • 주어진 n의 소인수를 구한 뒤, 각 소인수들의 (1-1/p)를 구하여 n에 곱해주면 서로소의 갯수를 구할 수 있다.

 

• 이 때, 모든 수에 대해 해주면 10^12이므로 메모리 초과가 발생한다.
  • 따라서, 에라토스테네스의 체와 같이 제곱근까지의 수까지 반복문을 돌리며
  • 소수를 찾으면 ANS -= ANS/P를 해주며 답을 구해간다.
• 오일러 피 함수만 안다면 간단한 문제이다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  


N = int(input())  
result = N  
i = 2  
while i ** 2 <= N:  
    if N % i == 0:  
        result *= (1 - (1/i))  
        while not N % i:  
            N //= i  
    i += 1  

if N > 1:  
    result *= 1 - 1 / N  

print(round(result))