[11689] GCD(n, k) = 1 (오일러 피, 서로소)

11689번: GCD(n, k) = 1

 

분석

1. 구하고자 하는 오일러 피의 범위만큼 리스트를 자기 자신의 인덱스 값으로 초기화
2. 2부터 시작해 현재 리스트의 값과 인덱스의 값이 같으면(소수) 현재 선택된 숫자k의 배수에 해당하는 수를 리스트에 끝까지 탐색하며 P[i]=P[i]-P[i]/k 연산을 수행 (i는 k의 배수)
3. 리스트의 끝까지 2를 반복하여 오일러 피 함수 완성

 

풀이

"""
자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오.
첫째 줄에 자연수 n (1 ≤ n ≤ 1012)이 주어진다.
"""
import math
n=int(input())
res=n

for p in range(2, int(math.sqrt(n))+1): # 제곱근까지만 진행
    if n%p==0: # 소인수인지
        res-=res/p
        while n%p==0:
            n/=p

if n>1:   # 반복문에서 제곱근까지만 탐색했으므로 1개의 소인수가 누락되는 케이스 처리
    res-=res/n

print(int(res))