C++で配列要素の積の約数の個数を数える方法

整数型の配列 arr[] が与えられたとき、そのすべての要素を掛け合わせた値の約数がいくつあるかを求めるのが本記事のテーマです。

配列とは、同じ型の要素を固定サイズで連続的に格納できるデータ構造の一種です。複数のデータをひとまとめに扱うために使われ、「同じ型の変数の集まり」として考えると理解しやすくなります。

具体例

入力: int arr[] = {2, 3}
出力: count is 4

解説: 配列の積は 2 × 3 = 6 です。6 の約数は 1, 2, 3, 6 の 4 個なので、答えは 4 となります。

入力: int arr[] = {2, 3, 5}
出力: count is 8

解説: 配列の積は 2 × 3 × 5 = 30 です。30 の約数は 1, 2, 3, 5, 6, 10, 15, 30 の 8 個なので、答えは 8 となります。

アルゴリズムの手順

1. 配列 arr[] を用意します。
2. sizeof 演算子などを使って配列の要素数（サイズ）を求めます。
3. 一時変数 temp を宣言し、1 で初期化します。
4. i を 0 から配列サイズ未満までループさせ、temp *= arr[i] ですべての要素の積を計算します。
5. 約数の個数を返す関数 divisors() を呼び出します。
6. divisors() 内では、i を 1 から N 以下までループさせ、N % i == 0 が成立するたびにカウントを 1 ずつ増やします。
7. 最終的なカウントを返し、結果を出力します。

C++ 実装例

#include <iostream>
using namespace std;

// 約数の個数を数える関数
int divisors(int N) {
    int result = 0;              // 結果を 0 で初期化
    for (int i = 1; i <= N; ++i) {
        if (N % i == 0) {        // i が N の約数ならば
            result++;            // カウントを増やす
        }
    }
    return result;
}

// 配列の全要素の積の約数を数える関数
int countmultiples(int arr_1[], int size) {
    int temp = 1;                // 積を計算するための変数
    for (int i = 0; i < size; ++i) {
        temp *= arr_1[i];
    }
    return divisors(temp);
}

// メイン関数
int main() {
    int arr_1[] = { 5, 10, 15 };
    int size = sizeof(arr_1) / sizeof(arr_1[0]);
    cout << "count is " << countmultiples(arr_1, size);
    return 0;
}

出力結果

上記のコードを実行すると、次の出力が得られます。

count is 16

この場合、配列の積は 5 × 10 × 15 = 750 となり、750 の約数はちょうど 16 個あります。

効率化のための補足

上記の divisors() 関数は 1 から N まで順番に調べるため、計算量は O(N) です。N が大きくなると処理時間が伸びるため、次のような改善が有効です。

• √N まで調べる方法： i が N の約数なら N / i も必ず約数になります。そこで 1 から √N まで調べて約数を 2 個ずつ数えれば、計算量を O(√N) に抑えられます（i² = N の場合は 1 個だけ加算します）。
• 素因数分解を利用する方法： 積を素因数分解し、各素因数の指数を e₁, e₂, … とすると、約数の個数は (e₁+1) × (e₂+1) × … という式で求められます。大きな数でも高速に計算できる強力な手法です。
• オーバーフローへの注意： 要素数が多い場合、積は急激に巨大になり、int 型ではすぐにオーバーフローします。必要に応じて long long 型を使用するか、積を直接計算せずに素因数ごとの指数を管理する設計にすると安全です。