C++で約数の個数が偶数か奇数かを判定するプログラム

はじめに

整数「n」が入力として与えられたとき、nの約数の総数が偶数であるか奇数であるかを判定するプログラムを、C++で作成する方法を解説します。

偶数と奇数とは

偶数とは、2でちょうど割り切れる整数のことです。例：0、8、-24

奇数とは、2で割り切れない整数のことです。例：1、7、-11、15

実行例

Input: 10
Output: Even

考え方（アルゴリズム）

nのすべての約数を求めて個数を数え、その数を2で割った余りを確認することで、偶数か奇数かを判定します。

約数を効率よく数えるポイントは、1から√n（平方根）までの範囲だけを調べればよいという点です。i が n の約数であれば、n/i も必ず n の約数になるため、1組につき2つずつカウントできます。ただし、i = n/i となる場合（i が √n と一致する場合）は、同じ約数を二重に数えないよう1つだけカウントします。

サンプルコード

#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;
}

補足：数学的な性質を活用した別解

実は、約数の個数が奇数になるのは、その数が完全平方数である場合だけです。これは、約数が通常「i」と「n/i」のペアで現れるのに対し、平方根の位置にある約数だけが自分自身とペアになり、単独でカウントされるためです。

この性質を利用すれば、約数を実際に数え上げることなく、「sqrt(n) が整数かどうか」をチェックするだけで偶奇を判定できる、より高速な実装も可能になります。