【C++】素因数の集合がXの素因数の集合の部分集合となる数をすべて出力する方法

本記事では、N個の整数からなる配列と整数Xが与えられたとき、素因数の集合がXの素因数の集合の部分集合となっている要素をすべて出力するアルゴリズムを、C++のコード例とともに解説します。

問題の概要

配列内の各数値について、その数を構成する素因数がすべてXの素因数に含まれる場合にのみ、その数値を出力対象とします。それ以外の数値は除外されます。

入力例・出力例

入力: X = 30、配列 = {2, 3, 6, 11, 14}
出力: 2 3 6

X = 30 = 2 × 3 × 5 なので、Xの素因数の集合は {2, 3, 5} です。

• 2: 素因数は {2} → 部分集合なので出力
• 3: 素因数は {3} → 部分集合なので出力
• 6: 素因数は {2, 3} → 部分集合なので出力
• 11: 素因数は {11} → 集合に含まれないため除外
• 14: 素因数は {2, 7} → 7が含まれないため除外

解法のアプローチ

この問題は、最大公約数（GCD）を利用するとシンプルかつ効率的に解くことができます。手順は以下の通りです。

1. 配列の各要素について、gcd(要素, X) を計算します。
2. gcd が 1 になるまで、要素を gcd で割り続けます。これにより、Xと共通する素因数がすべて取り除かれていきます。
3. 最終的に残った値が 1 であれば、その要素の素因数はすべてXの素因数に含まれていたことになるため、元の値を出力します。
4. 条件を満たす要素がひとつも存在しない場合は、その旨のメッセージを表示します。

C++での実装例

#include <bits/stdc++.h>
using namespace std;

void printPrimeSet(int a[], int n, int x){
    bool flag = false;
    for (int i = 0; i < n; i++) {
        int num = a[i];
        int g = __gcd(num, x);
        while (g != 1) {
            num /= g;
            g = __gcd(num, x);
        }
        if (num == 1) {
            flag = true;
            cout << a[i] << " ";
        }
    }
    if (!flag)
        cout << "There are no such numbers";
}

int main(){
    int x = 60;
    int a[] = { 2, 5, 10, 7, 17 };
    int n = sizeof(a) / sizeof(a[0]);
    cout << "Numbers whose set of prime numbers is subset of set of prime factor of " << x << "\n";
    printPrimeSet(a, n, x);
    return 0;
}

実行結果

X = 60 = 2² × 3 × 5 の場合、素因数の集合は {2, 3, 5} となります。配列 {2, 5, 10, 7, 17} のうち、条件を満たすのは次の3つの要素です。

• 2: 素因数は {2}
• 5: 素因数は {5}
• 10: 素因数は {2, 5}

一方、7と17はXの素因数に含まれないため除外されます。

Numbers whose set of prime numbers is subset of set of prime factor of 60
2 5 10

計算量の目安

GCDの計算にはユークリッドの互除法を用いており、1回の計算は O(log M)（Mは値の上限）で行えます。また、ループ内の除算では毎回値が少なくとも半分に減るため、反復回数は O(log M) 回に収まります。したがって、配列の要素数を N とすると、全体の計算量は O(N log² M) 程度となり、非常に効率的なアルゴリズムです。