C++で2つの数の共通素因数を求める方法

2つの整数 x と y が与えられ、これらの数に共通する素因数を求めることを考えます。共通素因数を見つけるには、まず2つの数の共通の約数を求め、その中から素数であるものを特定します。効率的に求めるには、最大公約数(GCD)を活用するのがポイントです。

具体例

入力 − x = 10、y = 20
出力 − 2つの数の共通素因数:2 5

説明 − 10と20の共通素因数は2と5のみです。

入力 − x = 34、y = 12
出力 − 2つの数の共通素因数:2

説明 − 34と12の共通素因数は2のみです。

アルゴリズムの流れ

• 2つの数 x と y の値を入力します。

• 共通素因数を求めるための関数を作成します。

• x と y の最大公約数(GCD)を格納する一時変数を宣言します。

• 2から始めて GCD 以下である間、i を1ずつ増やしながらループを実行します。

• ループ内で「prime[i] が真 かつ GCD % i == 0」であるかを判定します。

• 条件を満たしていれば i の値を出力します。

• 最終的な結果を出力します。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
#define MAX 100001
bool prime[MAX];
void SieveOfEratosthenes(){
    // ブール配列 "prime[0..n]" を作成し、すべての要素を true で初期化します。
    // prime[i] の値は、i が素数でない場合に最終的に false となります。
    memset(prime, true, sizeof(prime));
    // 0 と 1 は素数ではありません
    prime[0] = false;
    prime[1] = false;
    for (int p = 2; p * p <= MAX; p++){
        // prime[p] が true のままなら、p は素数です
        if (prime[p] == true){
            // p の倍数をすべて非素数として更新します
            for (int i = p * p; i <= MAX; i += p){
                prime[i] = false;
            }
        }
    }
}
// 2つの数の共通素因数を求める関数
void common_prime(int x, int y){
    // 与えられた2つの数の最大公約数(GCD)を求めます
    int g = __gcd(x, y);
    // g の素因数を検索します
    for (int i = 2; i <= (g); i++){
        // i が素数であり、かつ g の約数である場合
        if (prime[i] && g % i == 0){
            cout << i << " ";
        }
    }
}
// メイン関数
int main(){
    // エラトステネスの篩を作成
    SieveOfEratosthenes();
    int x = 20, y = 30;
    cout << "Common prime factor of two numbers are: ";
    common_prime(x, y);
    return 0;
}

出力

上記のコードを実行すると、以下の出力が得られます。

Common prime factor of two numbers are: 2 5