C++で指定範囲内の「約数がちょうどK個」の数を検索する方法

この記事では、3つの整数値 L、R、k が与えられたときに、指定された範囲 [L, R] 内で約数がちょうどk個である数の個数を求める方法を解説します。なお、約数のカウントには「1」と「その数自身」も含まれます。

入力例と出力例

入力

a = 3, b = 10, k = 3

出力

2

説明

3から10の範囲内で、約数がちょうど3個である数は次の通りです。
4 : 約数 = 1, 2, 4
9 : 約数 = 1, 3, 9

解法アプローチ

最もシンプルな解決策は、範囲内の各数について約数の個数を順番に数えていくことです。しかし、ここには重要な数学的な性質があります。

約数の個数が奇数になるのは、その数が完全平方数である場合だけです。これは、約数が通常ペア（d と n/d）で現れるためです。ただし完全平方数の場合、√n だけが自分自身とペアになり、結果として約数の総数が奇数になります。

この性質を利用すると、完全平方数のみを対象に約数を数えればよいことがわかります。これにより、計算量を大幅に削減でき、処理時間を短縮できます。そして、数えた約数の個数がkと一致した場合に、答えのカウントを1増やします。

C++での実装例

以下は、この解法の動作を示すプログラムです。

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

// 完全平方数かどうかを判定する関数
bool isPerfectSquare(int n) {
    int s = sqrt(n);
    return (s*s == n);
}

// 約数の個数を数える関数
int countDivisors(int n) {
    int divisors = 0;
    for (int i=1; i<=sqrt(n)+1; i++) {
        if (n%i==0) {
            divisors++;
            if (n/i != i)
                divisors++;
        }
    }
    return divisors;
}

// 範囲内で約数がk個の数をカウントする関数
int countNumberKDivisors(int a,int b,int k) {
    int numberCount = 0;
    for (int i=a; i<=b; i++) {
        if (isPerfectSquare(i))
            if (countDivisors(i) == k)
                numberCount++;
    }
    return numberCount;
}

int main() {
    int a = 3, b = 10, k = 3;
    cout<<"The count of numbers with K odd divisors is "<<countNumberKDivisors(a, b, k);
    return 0;
}

実行結果

The count of numbers with K odd divisors is 2

まとめ

この解法のポイントは、「約数の個数が奇数 ⇔ 完全平方数」という性質を活かし、判定対象を完全平方数に限定することで無駄な計算を省いている点です。約数の個数を数える際も、√n までループし、ペアとなる約数を同時にカウントすることで、O(√n) の計算量で効率的に処理できます。