指定した範囲内で約数がちょうどK個となる数を検索するC++プログラム

問題概要

この問題では、3つの整数 L、R、k が与えられます。目的は、与えられた範囲 [L, R] 内に存在する「約数の個数がちょうど k 個」である数をすべて数えることです。なお、1 とその数自身も約数としてカウントします。

具体例で問題を確認しましょう。

入力

a = 3, b = 10, k = 4

出力

2

説明

範囲 3〜10 の中で約数がちょうど 4 個ある数は以下の通りです。
6 : 約数 = 1, 2, 3, 6
8 : 約数 = 1, 2, 4, 8

解法アプローチ

最もシンプルな解法は、範囲内の各数について約数の個数を実際に数え上げる方法です。具体的には、[a, b] の範囲内のすべての整数に対して約数の個数を計算し、その個数が k と一致した場合にカウンターを 1 増やしていきます。

約数の個数を効率よく数えるポイントは、√n までだけループを回すことです。i が n の約数であれば、n/i も必ず n の約数になるため、1 回の判定で 2 つの約数を見つけられます。ただし、n が平方数の場合（i = n/i となる場合）は同じ約数を二重にカウントしないよう注意が必要です。

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

実装例

#include<bits/stdc++.h>
using namespace std;
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;
}
int countNumberKDivisors(int a,int b,int k) {
   int numberCount = 0;
   for (int i=a; i<=b; i++) {
      if (countDivisors(i) == k)
         numberCount++;
   }
   return numberCount;
}
int main() {
   int a = 3, b = 10, k = 4;
   cout<<"The count of numbers with "<<k<<" divisors is "<<countNumberKDivisors(a, b, k);
   return 0;
}

出力

The count of numbers with 4 divisors is 2

コードの解説

countDivisors 関数は、1 から √n+1 までの整数 i を順に調べ、n が i で割り切れる場合に約数をカウントします。このとき、n/i ≠ i であれば対応する約数 n/i も同時にカウントすることで、1 つの数の約数個数を O(√n) で求められます。countNumberKDivisors 関数では、範囲内の各数に対してこの関数を呼び出し、約数の個数が k と一致する数の総数を返しています。

計算量

時間計算量：O((R − L + 1) × √R)
空間計算量：O(1)