C 언어로 약수의 개수가 짝수인지 홀수인지 판별하는 프로그램

숫자 "n"이 입력으로 주어졌을 때, 이 프로그램은 n의 약수(제수)의 총 개수가 짝수인지 홀수인지 판별하는 문제입니다.

짝수(Even)는 2로 정확히 나누어 떨어지는 정수입니다. 예: 0, 8, -24
홀수(Odd)는 2로 나누어 떨어지지 않는 정수입니다. 예: 1, 7, -11, 15

입력: 10
출력: Even

문제 접근 방법

n의 모든 약수를 구한 뒤, 약수의 총 개수가 짝수인지 홀수인지 확인하면 됩니다. 즉, 모든 약수를 찾아 개수를 센 다음, 그 숫자를 2로 나누었을 때 나머지가 0인지 검사하는 방식입니다.

구현 예제

#include <iostream>
#include <math.h>
using namespace std;
int main() {
    int n = 10;
    int count = 0;
    for (int i = 1; i <= sqrt(n) + 1; i++) {
        if (n % i == 0)
            count += (n / i == i) ? 1 : 2;
    }
    if (count % 2 == 0)
        printf("Even\n");
    else
        printf("Odd\n");
    return 0;
}

코드 동작 원리

이 코드는 약수가 항상 쌍으로 존재한다는 성질을 활용합니다. 예를 들어 10의 경우 (1, 10), (2, 5)처럼 곱해서 n이 되는 두 수가 한 쌍을 이룹니다. 따라서 1부터 √n까지만 반복하면서 i가 n의 약수라면 개수를 2씩 더하고, 만약 i와 n/i가 같다면(즉, i² = n인 경우) 같은 약수를 중복해서 세지 않도록 1만 더합니다.

더 빠른 방법: 완전제곱수 활용

수학적으로 흥미로운 사실 하나를 알면 이 문제를 훨씬 간단하게 해결할 수 있습니다. 바로 약수의 개수가 홀수인 자연수는 오직 완전제곱수뿐이라는 점입니다. 대부분의 약수는 쌍을 이루기 때문에 개수가 짝수이지만, √n처럼 자기 자신과 짝을 이루는 약수는 완전제곱수에서만 존재하기 때문입니다.

따라서 n이 완전제곱수인지, 즉 √n이 정수인지만 확인하면 답을 바로 구할 수 있습니다.

int root = (int)sqrt(n);
if (root * root == n)
    printf("Odd\n");
else
    printf("Even\n");

시간 복잡도

반복문 방식은 O(√n)의 시간 복잡도를 가지며, 완전제곱수 판별 방식은 단 한 번의 제곱근 연산으로 해결할 수 있어 훨씬 더 효율적입니다.