C++で約数の個数が奇数になる数を指定範囲内で数える方法

このチュートリアルでは、指定された範囲の中から約数の個数が奇数となる数を数えるC++プログラムを紹介します。

具体的には、範囲の下限と上限が与えられ、その間に含まれる数のうち、約数の個数が奇数になっているものをすべてカウントするのが目的です。

数学的なポイント：約数の個数が奇数になるのは完全平方数だけ

一般に、整数 n の約数は d と n/d のペアで現れるため、その個数は偶数になります。しかし、完全平方数(1, 4, 9, 16, …)の場合だけは例外です。

例えば n = 9 の場合、約数は 1, 3, 9 の3つです。これは 3 × 3 = 9 となり、√n 自身が約数として1回だけ現れるため、約数の総数が奇数になります。

したがって、「約数の個数が奇数である数」を数えることは、「範囲内の完全平方数の個数」を数えることと同じです。

サンプルコード

#include <bits/stdc++.h>
using namespace std;

// 約数の個数が奇数である数を数える関数
int OddDivCount(int a, int b) {
    int res = 0;
    for (int i = a; i <= b; ++i) {
        int divCount = 0;
        // 各数値の約数をすべて調べる
        for (int j = 1; j <= i; ++j) {
            if (i % j == 0) {
                ++divCount;
            }
        }
        // 約数の個数が奇数ならカウント
        if (divCount % 2) {
            ++res;
        }
    }
    return res;
}

int main() {
    int a = 1, b = 10;
    cout << OddDivCount(a, b) << endl;
    return 0;
}

出力

3

コードの解説

このプログラムの処理の流れは以下の通りです。

1. 外側のループで、範囲 [a, b] 内の各数値 i を順番に取り出します。
2. 内側のループで、1 から i までの各数 j について「i を j で割り切れるか」を判定し、割り切れる場合は約数としてカウントします。
3. 約数の個数(divCount)が奇数であれば、結果(res)を1つ増やします。
4. 最終的な res の値を返します。

上記の例では範囲が 1〜10 なので、約数の個数が奇数になるのは 1(約数:1)、4(約数:1, 2, 4)、9(約数:1, 3, 9) の3つです。そのため出力は「3」となります。

より効率的な実装

上記の素朴な方法は計算量が大きく、範囲が広くなると非効率です。「約数の個数が奇数である数 = 完全平方数」という性質を利用すると、次のように簡潔かつ高速に書けます。

#include <bits/stdc++.h>
using namespace std;

// 完全平方数の個数を数えることで高速化
int OddDivCount(int a, int b) {
    int count = 0;
    for (int i = a; i <= b; ++i) {
        int root = (int)sqrt(i);
        if (root * root == i) {
            ++count;
        }
    }
    return count;
}

int main() {
    int a = 1, b = 10;
    cout << OddDivCount(a, b) << endl;
    return 0;
}

さらに、⌊√b⌋ − ⌊√(a−1)⌋ を計算するだけで O(1) で答えを求めることも可能です。例えば 1〜10 の場合、⌊√10⌋ = 3 なので答えは 3 になります。