C++で数の約数の積を求めるアルゴリズム

ある整数 n が与えられたとき、そのすべての約数を求め、それらの積を計算して結果として返すことを考えます。これが「数の約数の積を求める」という問題です。約数とは、その数を余りなく割り切ることができる数(1 を含む)のことです。たとえば、6 の約数は 1、2、3、6 です。

このタスクでは、与えられた数のすべての約数を掛け合わせた値を求めます。

入力例と出力例

入力 − n = 18
出力 − 5832
説明 − 1 × 2 × 3 × 6 × 9 × 18 = 5832

入力 − n = 9
出力 − 27
説明 − 1 × 3 × 9 = 27

問題を解くためのアプローチ

すべての約数を愚直に全探索すると O(n) の計算量が必要ですが、約数はペア(小さい方と大きい方)で現れる性質を利用すると、O(√n) で効率的に求められます。手順は以下の通りです。

• 入力として num を受け取ります。

• i = 1 から i * i <= num となるまでループします。

• num % i == 0(つまり i が約数)であるかを判定し、次のように処理します。

  • num / i == i の場合(i が平方根に相当する約数)、二重カウントを避けるため product = (product * i) % MAX のみを行います。

  • それ以外の場合は、product = (product * i) % MAX とし、さらに product = (product * num / i) % MAX として、ペアになるもう一方の約数も掛け合わせます。

• 最後に product を返します。

アルゴリズム

開始
関数 long long productfactor(int num)
    ステップ 1 → product を宣言し、1 で初期化する
    ステップ 2 → i = 1 から i * i <= num の間、i を増やしながら繰り返す
        もし num % i == 0 ならば、
            もし num / i == i ならば、
                product を (product * i) % MAX に設定する
            そうでなければ、
                product を (product * i) % MAX に設定する
                product を (product * num / i) % MAX に設定する
    ステップ 3 → product を返す
関数 int main()
    ステップ 1 → n を宣言し、9 で初期化する
    ステップ 2 → productfactor(n) の結果を出力する
終了

実装例

#include <stdio.h>
#define MAX 1000000000
// 約数の積を求める
long long productfactor(int num){
    long long product = 1;
    for (int i = 1; i * i <= num; i++){
        if (num % i == 0){
            // 同じ約数は一度だけ掛ける(平方数の場合の対策)
            if (num / i == i)
            product = (product * i) % MAX;
            // そうでなければ両方の約数を掛ける
            else {
                product = (product * i) % MAX;
                product = (product * num / i) % MAX;
            }
        }
    }
    return product;
}
int main(){
    int n = 9;
    printf("%lld\n", productfactor(n));
    return 0;
}

出力

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

27

このように、ループを √num までに限定することで、大きな数に対しても高速に約数の積を計算できます。なお、積が非常に大きくなる可能性があるため、オーバーフロー防止のために各ステップで MAX による剰余を取っている点にも注目してください。