기록방

👉 문제링크 11689번: GCD(n, k) = 1 자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 🔸 문제 분석 🔸 1부터 자연수 n까지의 범위에서, 최대공약수(GCD)가 1인 자연수의 개수를 구하는 문제이다. 다시 말하면 서로소의 개수를 구하는 문제이다. 🔸 문제 풀이 🔸 서로소 개수를 구하는 공식으로 오일러의 피 함수(Euler product formula; 오일러 곱 공식)을 사용한다. n의 소인수로 P[i] = P[i] - P[i]/K (i는 K의 배수) 연산을 반복한다. n이 소수이거나, n이 지수가 1인 소인수를 가지는 경우, 오일러 피 함수를 1회 더 적용한다. 🔸 코드 🔸 impo..