문제 설명
오일러 피(Euler’s totient function), 또는 φ(n)은 1과 n 사이의 정수 중 n과 서로소인 정수의 개수를 반환하는 함수입니다. 예를 들어, φ(9) = 6이며 그 이유는 1, 2, 4, 5, 7, 8이 9와 서로소이기 때문입니다.
이번 문제는 주어지는 정수 N에 대해 φ(N)을 계산하는 함수, calculateTotient를 작성하는 것입니다. 이 함수는 n이 1보다 크거나 같고, 10^6 이하일 때 정확한 φ(n)의 값을 출력해야 합니다.
문제 접근 방법
오일러 피를 계산하는 방법에는 여러 가지가 있지만, 제일 효율적인 방법 중 하나는 n의 소인수 분해를 사용하는 것입니다. 오일러 피 함수는 다음과 같이 정의될 수 있습니다:
- φ(p^k) = p^k – p^(k-1) (p는 소수, k는 자연수)
- φ(n) = n × (1 – 1/p1) × (1 – 1/p2) × … × (1 – 1/pk) (n의 소인수 p1, p2, …, pk)
알고리즘 단계
- 입력 값 N을 가져온다.
- N의 소인수를 찾는다.
- 각 소인수에 대해 φ(n) 공식을 적용하여 결과를 계산한다.
- 결과를 반환한다.
실제 코드 구현
다음은 자바스크립트로 작성된 calculateTotient 함수의 구현입니다. 이 함수는 입력받은 n에 대해서 오일러 피 값을 반환합니다.
function gcd(a, b) {
return b === 0 ? a : gcd(b, a % b);
}
function calculateTotient(n) {
let result = n; // 초기 값은 n
for (let p = 2; p * p <= n; p++) {
if (n % p === 0) { // p가 n의 소인수일 경우
while (n % p === 0) {
n /= p;
}
result *= (p - 1);
result /= p; // 오일러 피 공식 적용
}
}
if (n > 1) { // n이 소수인 경우
result *= (n - 1);
result /= n;
}
return result;
}
console.log(calculateTotient(9)); // 출력: 6
코드 설명
– gcd 함수는 두 숫자의 최대공약수를 계산합니다. 이 함수는 기본적인 알고리즘으로, 소인수 분해를 위해 사용됩니다.
– calculateTotient 함수에서는 변수 result를 n으로 초기화하여 이후 소인수에 대한 변화를 반영합니다.
– for 루프를 통해 2부터 n의 제곱근까지의 모든 수 p를 검사하여 n이 p의 배수인 경우 소인수로 인식합니다.
– 마지막으로 n이 1보다 큰 경우, 즉 n이 소수인 경우에 대해 추가 연산을 수행하여 결과를 얻습니다.
결론
이번 강좌에서는 오일러 피를 계산하는 방법에 대해 알아보았습니다. 알고리즘 문제를 해결하기 위해 소인수 분해라는 수학적 개념을 이용하는 것이 얼마나 중요한지 이해하셨길 바랍니다. 이와 같은 토픽을 활용하여 자바스크립트 코딩 테스트를 준비해보세요.