PHP로 숫자의 약수 개수가 짝수인지 홀수인지 판별하는 방법

주어진 숫자의 전체 약수 개수가 짝수인지 홀수인지 확인하고 싶다면, 아래와 같이 PHP 코드를 작성하면 됩니다.

예제

<?php
function divisor_count($my_val)
{
    $my_count = 0;
    for ($i = 1; $i <= sqrt($my_val) + 1; $i++)
    {
        if ($my_val % $i == 0)
        $my_count += ($my_val / $i == $i)? 1 : 2;
    }
    if ($my_count % 2 == 0)
        echo "It is an even number\n";
    else
        echo "It is an odd number\n";
}
divisor_count(100);
?>

출력 결과

It is an odd number

코드 동작 방식

위 코드에서는 divisor_count라는 함수를 정의하여, 매개변수로 전달받은 숫자의 약수 개수를 계산합니다. 함수 내부에서는 1부터 해당 숫자의 제곱근까지 반복하면서 나누어 떨어지는 수를 찾습니다. 이때 제곱근 자체가 약수인 경우(즉, 완전제곱수인 경우)에는 카운트를 1만 증가시키고, 그 외의 경우에는 서로 짝을 이루는 두 개의 약수가 동시에 발견되므로 카운트를 2씩 증가시킵니다.

약수 개수를 모두 구한 뒤에는 이 값을 2로 나눈 나머지를 확인합니다. 나머지가 0이면 약수 개수가 짝수이므로 "It is an even number"를 출력하고, 그렇지 않으면 "It is an odd number"를 출력합니다. 위 예제에서는 100을 입력했으며, 100의 약수는 1, 2, 4, 5, 10, 20, 25, 50, 100으로 총 9개이기 때문에 홀수라는 결과가 출력됩니다.

수학적 배경: 완전제곱수만 홀수 개의 약수를 가집니다

약수는 일반적으로 d × (N/d) = N의 관계로 쌍을 이루기 때문에, 대부분의 숫자는 짝수 개의 약수를 가집니다. 하지만 완전제곱수(예: 4, 9, 16, 25, 100)는 제곱근이 자기 자신과 짝을 이루므로 유일하게 홀수 개의 약수를 갖습니다. 따라서 어떤 수가 완전제곱수인지만 확인해도 약수 개수의 홀짝 여부를 바로 알 수 있습니다.

성능 참고 사항

이 알고리즘은 1부터 √n까지만 검사하므로 시간 복잡도가 O(√n)입니다. 1부터 n까지 모든 숫자를 하나씩 확인하는 O(n) 방식보다 훨씬 효율적이며, 큰 숫자를 다룰 때 특히 유용합니다.