C++でN以下のすべての半素数を出力する方法

この記事では、整数 N が与えられたとき、N 以下のすべての半素数を出力する方法を解説します。

半素数とは

半素数（semi-prime number）とは、2つの異なる素数の積で表される数のことです。

具体的な例を見てみましょう。

• 21 = 3 × 7 → 半素数である
• 25 = 5 × 5 → 半素数ではない（同じ素数の積のため）

問題の例

N 以下の半素数をすべて求める例を示します。

入力: N = 15
出力: 6 10 14 15

解法のアプローチ

この問題を解くには、N 以下の各数について、それがちょうど2つの異なる素因数を持つかどうかを確認します。

ヒント: 最小の半素数は 6 なので、アルゴリズムの探索は 6 から始めても構いません。

C++での実装

#include <bits/stdc++.h>
using namespace std;
vector<int>generateSemiPrimeNumbers(int n){
    int index[n + 1];
    for (int i = 1; i <= n; i++)
        index[i] = i;
    int countDivision[n + 1];
    for (int i = 0; i < n + 1; i++)
        countDivision[i] = 2;
    for (int i = 2; i <= n; i++) {
        if (index[i] == i && countDivision[i] == 2) {
            for (int j = 2 * i; j <= n; j += i) {
                if (countDivision[j] > 0) {
                    index[j] = index[j] / i;
                    countDivision[j]--;
                }
            }
        }
    }
    vector<int> semiPrime;
    for (int i = 2; i <= n; i++) {
        if (index[i] == 1 && countDivision[i] == 0) semiPrime.push_back(i);
    }
    return semiPrime;
}
int main(){
    int n = 15;
    cout<<"Semi-prime numbers less that or equal to "<<n<<"are :\n";
    vector<int>semiPrime = generateSemiPrimeNumbers(n);
    for (int i = 0; i < semiPrime.size(); i++)
        cout<<semiPrime[i]<<"\t";
    return 0;
}

アルゴリズムの仕組み

この実装では、エラトステネスの篩に似た考え方を利用しています。処理の流れは以下の通りです。

1. index[i] には初期値として i 自身を設定し、countDivision[i] はすべて 2 で初期化します。
2. i が素数の場合（index[i] == i のまま残っている場合）、その倍数 j に対して index[j] を i で割り、countDivision[j] を 1 減らします。
3. 処理終了後、index[i] == 1 かつ countDivision[i] == 0 を満たす i は、ちょうど2つの異なる素数で割り切れた数、すなわち半素数です。

例えば 15 = 3 × 5 の場合、素数 3 と 5 でそれぞれ1回ずつ割られるため index[15] は 1 になり、半素数と判定されます。一方、12 = 2 × 2 × 3 のように素因数に重複がある数は、条件を満たさず半素数から除外されます。

実行結果

15 以下の半素数は以下の通りです。

6 10 14 15

まとめ

半素数の判定は、素因数分解をその都度行うのではなく、篩のような前処理で各数の素因数の個数を記録しておくと効率的に求められます。この手法は計算量が O(N log log N) 程度に抑えられ、N が大きい場合でも高速に動作します。