C/C++で数の一意な素因数の積を求めるプログラム

一意な素因数とは

一意な素因数（ユニークな素因数）とは、ある数の約数の中で、それ自体が素数であるものを指します。本記事では、与えられた整数に対して、重複しないすべての素因数を掛け合わせた積を求める方法を解説します。

なお、素数とは「1とその数自身」の2つしか約数を持たない数のことです。

問題を例で理解する

まず、具体的な例を使って問題を整理しましょう。

例として n = 1092 を考えます。この数の一意な素因数の積を求めます。

• 1092 の素因数：2、3、7、13
• これらの積：2 × 3 × 7 × 13 = 546

Input: n = 10
Output: 10

出力の説明

入力された数は 10 です。10 の素因数は 2 と 5 のみであるため、その積は 2 × 5 = 10 となります。

アルゴリズムのアプローチ

最もシンプルな方法は、以下の手順に従うものです。

1. i = 2 から n までループを回す。
2. i が n の約数であるか（n % i == 0）を確認する。
3. i が約数であれば、さらに i 自身が素数かどうかを判定する。
4. i が素数であれば、結果を格納する product 変数に i を掛ける。
5. i = n になるまでこの処理を繰り返す。

この方法では、各候補について約数判定と素数判定を行うため、計算量はやや大きくなりますが、ロジックが分かりやすく実装も簡単です。

C++での実装例

#include <iostream>
using namespace std;
int main() {
    int n = 10;
    long long int product = 1;
    for (int i = 2; i <= n; i++) {
        if (n % i == 0) {
            int isPrime = 1;
            for (int j = 2; j <= i / 2; j++) {
                if (i % j == 0) {
                    isPrime = 0;
                    break;
                }
            }
            if (isPrime) {
                product = product * i;
            }
        }
    }
    cout << product;
    return 0;
}

コードのポイント

• 積のオーバーフローを防ぐため、結果は long long int 型で保持しています。
• 内側のループで 2 から i/2 まで調べることで、i が素数かどうかを判定しています。
• 素因数が見つかるたびに product に掛け合わせることで、最終的に一意な素因数の積が得られます。

より大きな数を扱う場合は、平方根までの試し割りや、素因数分解を用いた効率的なアルゴリズムへの置き換えも検討すると良いでしょう。