[알고리즘] 백준 11689 파이썬 - GCD(n,k)=1

 

11689번: GCD(n, k) = 1

문제

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

 

문제풀이

#01
def Euler(n):
    ans=n
    for i in range(2,round(n**0.5)+1):
    	#02
        if n%i==0:
            while n%i==0:
                n//=i
            ans*=1-(1/i)
    #03
    if n>1:
        ans*=1-(1/n)
    return ans
n=int(input())
#04
ans=Euler(n)
print(round(ans))

- #01 : 오일러 피 함수를 구현한 것이다. (아래 링크를 참조)

오일러 파이 함수와 오일러 정리

- #02 : n의 서로소를 구하고 오일러 피함수의 공식대로 1-(1/i)를 해준다.

- #03 : 만약 위의 while문을 끝낸 n이 1보다 크다면 최종적으로 ans에 1-(1/n)을 해준다.

- #04 : 구한 값을 출력해준다.