【C/C++】数の一意な素因数の積を効率的に求めるプログラム

この記事では、ある整数の一意な素因数（重複を除いた素因数）の積を効率的に求める方法を解説します。例として n = 1092 を考えてみましょう。1092 を素因数分解すると 2 × 2 × 3 × 7 × 13 となり、一意な素因数は {2, 3, 7, 13} です。したがって、その積は 2 × 3 × 7 × 13 = 546 となります。

アルゴリズムの考え方

この問題を解くには、以下の手順に従います。

• 数が 2 で割り切れる場合は、積に 2 を掛けたうえで、数が 2 で割り切れなくなるまで繰り返し 2 で割ります。これにより、以降の 2 はすべて無視されます。

• この時点で数は必ず奇数になっています。そこで 3 から数の平方根までの範囲を奇数のみ（2 ずつ増やしながら）調べ、現在の値 i で割り切れるならば積に i を掛け、数を i で割ります。さらに i で割り切れなくなるまで割り続けることで、同じ素因数の重複を除外します。

• 最後に、残った数が 2 より大きければ、それはまだ処理されていない素因数なので、積にその数を掛けます。

理解を深めるために、アルゴリズムを擬似コードで確認してみましょう。

アルゴリズム

uniquePrimeProduct(n)

begin
    prod := 1
    if n is divisible by 2, then
        prod := prod * 2
        n := n / 2
    end if
    while n is divisible by 2, do
        n := n / 2
    done
    for i := 3 to √n, increase i by 2, do
        if n is divisible by i, then
            prod := prod * i
            n := n / i
        end if
        while n is divisible by i, do
            n := n / i
        done
    done
    if n > 2, then
        prod := prod * n
    end if
end

C言語での実装例

#include<stdio.h>
#include<math.h>
int uniquePrimeProduct(int n){
    int i, prod = 1;
    if(n % 2 == 0){
        prod *= 2;
        n = n/2;
    }
    while(n % 2 == 0){ // 以降の2をスキップ
        n = n/2;
    }
    for(i = 3; i <= sqrt(n); i=i+2){ // 奇数のみを調べるためiは2ずつ増加
        if(n % i == 0){
            prod *= i;
            n = n/i;
        }
        while(n % i == 0){ // 以降の同じ因数をスキップ
            n = n/i;
        }
    }
    if(n > 2){
        prod *= n;
    }
    return prod;
}
int main() {
    int n;
    printf("Enter a number: ");
    scanf("%d", &n);
    printf("Product of prime factors: %d", uniquePrimeProduct(n));
}

実行結果

Enter a number: 1092
Product of prime factors: 546

計算量について

このアルゴリズムは、候補となる約数を 3 から √n までの奇数だけに絞って調べる「試し割り法」をベースにしているため、時間計算量は O(√n) となります。大きな数でも比較的高速に一意な素因数の積を求められるのが特徴です。