오일러 𝜑(피 또는 파이) 함수, 서로소 개수 구하기
서로소란 1 을 제외하고 공약수가 없는 두 수의 관계입니다. 오일러 피함수 φ(n)은 n이하의 자연수 중 n과 서로소인 자연수의 개수를 의미하는 함수입니다. 예를 들어 φ(6)은 2로 1과 5의 서로소가 있음을 의미합니다. 모든 자연수는 소수들의 (prime) 곱으로 표현 할 수 있습니다. 예를들어 16은 2^4 로 표현할 수 있고 15는 3^1 * 5^1 로 나타낼 수 있습니다. φ(16)은 2, 4, 6, 8, 10, 12, 14, 16을 제외한 나머지 자연수와 서로소입니다. 여기서 알 수 있는 사실은, 자연수를 구성하는 소수들의 배수는 전부 서로소가 아닙니다. 즉, φ(16) = 16 - (16/2) = 8개로 구할 수 있습니다. ( n 이하의 k의 배수의 개수는 n/k로 구할 수 있습니다, 나머지..
2020. 8. 13.
