C++で配列内に他のすべての要素と互いに素な要素が存在するかを判定する方法

問題の概要

正の整数からなる配列 A[] が与えられます。ここで、各要素は 2 ≤ A[i] ≤ 10⁶ を満たすものとします。求めたいのは、配列内に「他のすべての要素と互いに素（coprime）なペアを形成できる要素」が少なくとも1つ存在するかどうかの判定です。

例として、配列 {2, 8, 4, 10, 6, 7} を考えてみましょう。この場合、7 は配列内の他のすべての要素（2, 8, 4, 10, 6）と互いに素であるため、条件を満たす要素が存在します。

効率的な解法のアプローチ

この問題を効率的に解く鍵は、配列内の各整数についてすべての素因数を求めることです。ある要素が他のどの要素とも共通の素因数を持たないのであれば、その要素は必ず他のすべての要素と互いに素なペアを形成できます。

具体的には、次の手順で判定を行います。

• エラトステネスの篩の要領で、1〜10⁶ までの各整数の「最小素因数」を前計算しておきます。
• 配列の各要素を最小素因数を利用して素因数分解し、現れた素因数の出現回数をハッシュテーブルに記録します。
• 各要素について、その素因数が他の要素でも使われていないか（出現回数が1回のみか）を確認します。すべての素因数がその要素に固有であれば、他のすべての要素と互いに素であると判定できます。

この手法により、各要素の素因数分解は O(log A[i]) で行え、全体としても非常に効率的に動作します。

サンプルコード

#include <iostream>
#define MAX 1000001
using namespace std;
int smallPrimeFactor[MAX];
// 素因数の出現回数を格納するハッシュ
int hash1[MAX] = { 0 };
void getSmallestPrimeFactor() {
    smallPrimeFactor[1] = 1;
    for (int i = 2; i < MAX; i++)
        smallPrimeFactor[i] = i;
    for (int i = 4; i < MAX; i += 2)
        smallPrimeFactor[i] = 2;
    for (int i = 3; i * i < MAX; i++) {
        if (smallPrimeFactor[i] == i) {
            for (int j = i * i; j < MAX; j += i)
                if (smallPrimeFactor[j] == j)
                    smallPrimeFactor[j] = i;
        }
    }
}
void factorizationResult(int x) {
    int temp;
    while (x != 1) {
        temp = smallPrimeFactor[x];
        if (x % temp == 0) {
            hash1[smallPrimeFactor[x]]++;
            x = x / smallPrimeFactor[x];
        }
        while (x % temp == 0)
            x = x / temp;
    }
}
bool hasCommonFactors(int x) {
    int temp;
    while (x != 1) {
        temp = smallPrimeFactor[x];
        if (x % temp == 0 && hash1[temp] > 1)
            return false;
        while (x % temp == 0)
            x = x / temp;
    }
    return true;
}
bool hasValueToFormCoPrime(int arr[], int n) {
    getSmallestPrimeFactor();
    for (int i = 0; i < n; i++)
        factorizationResult(arr[i]);
    for (int i = 0; i < n; i++)
        if (hasCommonFactors(arr[i]))
            return true;
    return false;
}
int main() {
    int arr[] = { 2, 8, 4, 10, 6, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
    if (hasValueToFormCoPrime(arr, n))
        cout << "There is a value, that can form Co-prime pairs with all other elements";
    else
        cout << "There is no value, that can form Co-prime pairs with all other elements";
}

コードのポイント

• getSmallestPrimeFactor()：篩を使って各整数の最小素因数を前計算します。偶数はあらかじめ 2 に設定し、処理を高速化しています。
• factorizationResult()：最小素因数を繰り返し除算することで素因数分解を行い、各素因数の出現回数をハッシュに記録します。
• hasCommonFactors()：ある要素の素因数がハッシュ内で2回以上出現している（＝他の要素と共有されている）場合は false を返します。

サンプル配列 {2, 8, 4, 10, 6, 7} の場合、7 は素数であり、その素因数「7」は配列全体で1回しか現れないため、7 が他のすべての要素と互いに素であると正しく判定されます。

実行結果

There is a value, that can form Co-prime pairs with all other elements