C++で配列要素のLCM（最小公倍数）の素因数を効率的に求める方法

問題の概要

この問題では、1 ≤ arr[i] ≤ 10¹² の範囲の整数からなる配列が与えられます。目的は、配列内のすべての要素の最小公倍数（LCM）に含まれるすべての素因数を出力することです。

入出力例

入力: array = {2, 5, 15}
出力: 2 3 5
説明: LCM = 30
30の素因数分解 = 2 × 3 × 5

解決のアプローチ

素直に考えると、まず配列の全要素のLCMを計算し、そのLCMを素因数分解して素数を列挙する、という流れになります。

しかし、10¹²オーダーの巨大な数を含む配列のLCMを直接計算すると、結果が桁違いに大きくなり、計算コストが非常に重くなってしまいます。そこで、別の視点から問題を解く必要があります。

ここで鍵となるのが、「各数の素因数は、それらの数のLCMの素因数でもある」という性質です。この性質を利用すれば、LCMを実際に計算しなくても、配列の各要素を素因数分解して現れた素因数を集めるだけで答えが得られます。

具体的な手順は以下のとおりです。

1. サンダラムの篩（Sieve of Sundaram）アルゴリズムを使って、10⁶（= √10¹²）までの素数を事前に生成する。
2. 配列の各要素を素因数分解し、現れた素因数をフラグ配列に記録する。
3. フラグが立っている素因数をすべて出力する。

C++による実装

以下は、この解法を実装したサンプルプログラムです。

#include <bits/stdc++.h>
using namespace std;
const int MAX = 1000000;
typedef long long int ll;
vector <int> primeNumbers;
void findPrimeNumbers() {
    int n = MAX;
    int nNew = (n)/2;
    bool marked[nNew + 100];
    memset(marked, false, sizeof(marked));
    int tmp=sqrt(n);
    for (int i=1; i<=(tmp-1)/2; i++)
        for (int j=(i*(i+1))<<1; j<=nNew; j=j+2*i+1)
            marked[j] = true;
    primeNumbers.push_back(2);
    for (int i=1; i<=nNew; i++)
    if (marked[i] == false)
    primeNumbers.push_back(2*i + 1);
}
void printPrimeLCM(ll arr[], int n ) {
    findPrimeNumbers();
    int factors[MAX] = {0};
    for (int i=0; i<n; i++) {
        ll copy = arr[i];
        int sqr = sqrt(copy);
        for (int j=0; primeNumbers[j]<=sqr; j++){
            if (copy%primeNumbers[j] == 0){
                while (copy%primeNumbers[j] == 0)
                copy = copy/primeNumbers[j];
                factors[primeNumbers[j]] = 1;
            }
        }
        if (copy > 1)
        factors[copy] = 1;
    }
    if (factors[2] == 1)
        cout<<2<<"\t";
    for (int i=3; i<=MAX; i=i+2)
        if (factors[i] == 1)
            cout<<i<<"\t";
}
int main() {
    ll arr[] = {20, 10, 15, 60};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout<<"配列の数のLCMに含まれる素因数 :\n";
    printPrimeLCM(arr, n);
    return 0;
}

出力結果

配列の数のLCMに含まれる素因数 :
2  3   5

まとめ

LCMそのものを計算せずに、各要素の素因数を個別に集めることで、巨大な数を直接扱うことなくLCMの素因数を効率的に求められます。素数の生成はサンダラムの篩によって高速に行え、10¹²オーダーの要素を含む配列にも対応できる実用的な手法です。