C++で1〜nの範囲にあるすべての数の約数の個数を求める方法

この問題では、整数Nが与えられ、1からnまでの範囲に含まれるすべての数について、それぞれの約数の個数を求めることが課題となります。

問題の例

具体例を見てみましょう。

入力 : N = 7
出力 : 1 2 2 3 2 4 2

N = 7の場合、1の約数は「1」の1個、2の約数は「1, 2」の2個、3の約数は「1, 3」の2個、4の約数は「1, 2, 4」の3個…というように、各数の約数の個数を順に出力します。

解法アプローチ1：各数ごとに約数を数える方法

最もシンプルな解法は、1からNまでの各数に対して、実際に割り切れる数を順番にカウントしていく方法です。各数iについて、2からiまでの値で順に割りを試し、余りが0になる回数を数えます。

サンプルコード1

#include <iostream>
using namespace std;
int countDivisor(int N){
    int count = 1; // 1は必ず約数なので初期値を1とする
    for(int i = 2; i <= N; i++){
       if(N % i == 0)
           count++;
    }
    return count;
}
int main(){
    int N = 8;
    cout<<"1から"<<N<<"までの各数の約数の個数 : ";
    cout<<"1 ";
    for(int i = 2; i <= N; i++){
       cout<<countDivisor(i)<<" ";
    }
    return 0;
}

出力結果

1から8までの各数の約数の個数 : 1 2 2 3 2 4 2 4

この方法は直感的で理解しやすい反面、各数について約数の判定を行うため、計算量はO(N²)となり、Nが大きくなると処理時間が増加します。

解法アプローチ2：倍数を使った効率的な方法（ふるい法）

より効率的なアプローチとして、「エラトステネスのふるい」と似た考え方を利用する方法があります。

手順は以下の通りです。

1. サイズ(N+1)の配列を作成し、すべての要素を1で初期化します（すべての数は少なくとも約数「1」を持つため）。
2. iを2からNまで順に走査し、iの倍数にあたる配列の要素をすべてインクリメントします。
3. 最終的に、配列の各要素にはその位置の数の約数の個数が格納されます。

この方法では、各約数がその倍数すべてに寄与するという性質を利用するため、計算量はO(N log N)程度に抑えられ、大幅な高速化が期待できます。

サンプルコード2

#include <iostream>
using namespace std;
void countDivisors(int N){
    int arr[N+1];
    // すべての要素を1で初期化
    for(int i = 0; i <= N; i++)
       arr[i] = 1;
    // iの倍数すべてのカウントを増やす
    for (int i = 2; i <= N; i++) {
       for (int j = 1; j * i <= N; j++)
           arr[i * j]++;
    }
    // 結果を出力
    for (int i = 1; i <= N; i++)
       cout<<arr[i]<<" ";
}
int main(){
    int N = 8;
    cout<<"1から"<<N<<"までの各数の約数の個数 : ";
    countDivisors(N);
    return 0;
}

出力結果

1から8までの各数の約数の個数 : 1 2 2 3 2 4 2 4

まとめ

1〜nの範囲のすべての数の約数の個数を求めるには、大きく分けて2つの方法があります。

• 単純な全探索： 各数ごとに約数を数える。実装は簡単だが、計算量はO(N²)。
• ふるい的な手法： 倍数ごとにカウントを増やす方式。計算量はO(N log N)程度で、大きなNでも高速に動作する。

競技プログラミングや大量のデータを扱う場面では、後者のふるい的なアプローチを採用することをおすすめします。