【C++】積が指定した値になる2つの異なる素数を見つける方法

はじめに

このチュートリアルでは、与えられた積(掛け算の結果)となる2つの異なる素数を見つけるC++プログラムを作成します。まず、具体例を見てみましょう。

入力: 21
出力: 3 7

積が21になる素数の組み合わせは「3と7」です。この問題を効率よく解くには、与えられた数より小さいすべての素数を事前に求めておくのがポイントです。素数表さえあれば、あとは組み合わせを確認するだけでペアを発見できます。

アルゴリズムの手順

以下の手順に従って問題を解いていきます。

• 積となる数値nと、範囲内の各数が素数かどうかを記録するbool型配列を用意します。
• エラトステネスの篩を使って、n未満のすべての素数を求めます。
• 2からnまで繰り返し処理を行います。
  • 現在の数iが素数であり、n / i も素数である場合、両者が異なる数かどうかを確認します。
  • 異なる数であれば、そのペアとして出力します。

サンプルコード

それでは、実際のコードを見てみましょう。

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

// エラトステネスの篩で素数表を作成する
void primes(int n, bool primeStatus[]) {
    primeStatus[0] = primeStatus[1] = false;
    for (int i = 2; i <= n; i++) {
        primeStatus[i] = true;
    }
    for (int i = 2; i * i <= n; i++) {
        if (primeStatus[i] == true) {
            for (int j = i * 2; j <= n; j += i)
                primeStatus[j] = false;
        }
    }
}

int main() {
    int n = 21;
    bool primeStatus[n + 1], pairsFound = false;
    primes(n, primeStatus);

    // 素数ペアを探索する
    for (int i = 2; i < n; i++) {
        int pair = n / i;
        if (primeStatus[i] && primeStatus[pair] && pair != i && pair * i == n) {
            cout << i << " " << pair << endl;
            pairsFound = true;
            break;
        }
    }

    // ペアが見つからなかった場合
    if (!pairsFound){
        cout << "No pairs";
    }
    return 0;
}

実行結果

上記のコードをコンパイルして実行すると、次の出力が得られます。

3 7

アルゴリズムのポイント

このアプローチの計算量を見てみましょう。エラトステネスの篩による素数表の作成は O(n log log n)、ペアの探索は O(n) で行えるため、全体として非常に効率的な手法です。

なお、2つの異なる素数の積で表される数は「半素数(セミプライム)」と呼ばれます。この性質はRSA暗号などの公開鍵暗号方式の基礎にも関わる重要な概念なので、合わせて覚えておくと良いでしょう。

まとめ

本チュートリアルでは、エラトステネスの篩を活用して、積が指定した値になる2つの異なる素数のペアを効率よく見つける方法を学びました。チュートリアルの内容について質問がある場合は、ぜひコメント欄でお知らせください。