11689번: GCD(n, k) = 1 자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 자연수 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 : 오일러 피 함..
