C++で与えられた積になる2つの異なる素数を見つける方法

この記事では、与えられた積（掛け算の結果）と等しくなる2つの異なる素数を見つけるC++プログラムについて解説します。

具体的には、1つの整数値が与えられたとき、その積がちょうど入力値と一致するような2つの素数のペアを見つけることが課題です。例えば入力が「35」であれば、5 × 7 = 35 が成立するため「5 7」が出力されます。条件を満たすペアが存在しない場合は、その旨を報告します。

アルゴリズムの考え方

この問題は、次の手順で効率的に解決できます。

1. 素数表の作成： エラトステネスの篩（ふるい）を用いて、N未満のすべての素数を事前に求めておきます。
2. ペアの探索： 2からN未満までの各整数 i について、「i が素数であること」「商 n / i も素数であること」「i × (n / i) = n が成り立つこと」「i ≠ n / i であること（2つの数が異なること）」という4つの条件を確認します。
3. 判定： すべての条件を満たすペアが見つかればそれを出力し、1つも存在しなければ「No prime pair exist（素数のペアは存在しない）」と表示します。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
//generating prime numbers less than N.
void findingPrimeNumbers(int n, bool calcPrime[]) {
    calcPrime[0] = calcPrime[1] = false;
    for (int i = 2; i <= n; i++)
        calcPrime[i] = true;
    for (int p = 2; p * p <= n; p++) {
        if (calcPrime[p] == true) {
            for (int i = p * 2; i <= n; i += p)
                calcPrime[i] = false;
        }
    }
}
//printing the valid prime pair
void calcPairPrime(int n) {
    int flag = 0;
    bool calcPrime[n + 1];
    findingPrimeNumbers(n, calcPrime);
    for (int i = 2; i < n; i++) {
        int x = n / i;
        if (calcPrime[i] && calcPrime[x] and x != i and x * i == n) {
            cout << i << " " << x;
            flag = 1;
            return;
        }
    }
    if (!flag)
        cout << "No prime pair exist";
}
int main() {
    int n = 24;
    calcPairPrime(n);
    return 0;
}

出力

No prime pair exist

コードの解説

findingPrimeNumbers関数： エラトステネスの篩を実装した関数です。まず0と1を非素数としてマークし、2以降をすべて素数候補とします。その後、2から順に各素数の倍数を除外していくことで、N以下の素数を効率よく判定できます。

calcPairPrime関数： 作成した素数表をもとに、2からN未満までの整数 i を順番に調べます。前述の4条件をすべて満たす最初のペアを見つけたら即座に出力して処理を終了します。フラグ変数 flag は、ペアが見つかったかどうかを記録するために使われています。

main関数： サンプルでは n = 24 を渡しています。24 = 2 × 12 = 3 × 8 = 4 × 6 と分解できますが、いずれの場合も片方または両方が素数ではないため、条件を満たすペアは存在せず「No prime pair exist」が出力されます。

ペアが存在する場合の例

例えば n = 21 の場合は 3 × 7 = 21 が成立するため、プログラムは「3 7」を出力します。同様に n = 35 なら「5 7」、n = 6 なら「2 3」となります。

計算量

エラトステネスの篩による素数生成は O(n log log n)、ペアの線形探索は O(n) となるため、本アルゴリズム全体の時間計算量は O(n log log n) となります。大きな入力値に対しても高速に動作するのが特徴です。