C++で1からNまでの準素数（Almost Prime）の個数を求める方法

ある数 N が与えられたとき、1からNまでの範囲に含まれる「準素数（almost prime）」の個数を求める問題を考えてみましょう。準素数とは、異なる素因数をちょうど2つ持つ数のことです。素因数以外の約数（合成数の約数）はいくつあっても構いませんが、その中に含まれる素因数は正確に2種類である必要があります。

例えば、Nが10の場合、出力は2になります。これは、条件を満たす数が 6（= 2 × 3）と 10（= 2 × 5）の2つしか存在しないためです。

アプローチ：エラトステネスの篩を活用する

この問題を効率的に解くには、エラトステネスの篩（Sieve of Eratosthenes）を使って素数判定を事前に行い、その後、各数について素因数の個数を数えていく方法が有効です。以下の実装例を見て、処理の流れを確認してみましょう。

実装例

#include<iostream>
#define N 100005
using namespace std;
bool prime[N];
void SieveOfEratosthenes() {
    for(int i = 0; i<N; i++)
    prime[i] = true;
    prime[1] = false;
    for (int i = 2; i * i < N; i++) {
       if (prime[i] == true) {
          for (int j = i * 2; j < N; j += i)
             prime[j] = false;
       }
    }
}
int countAlmostPrime(int n) {
    int result = 0;
    for (int i = 6; i <= n; i++) {
       int div_count = 0;
       for (int j = 2; j * j <= i; j++) {
          if (i % j == 0) {
             if (j * j == i) {
                if (prime[j])
                   div_count++;
             }else {
                if (prime[j])
                   div_count++;
                if (prime[i / j])
                   div_count++;
             }
          }
       }
       if (div_count == 2)
          result++;
    }
    return result;
}
int main() {
    SieveOfEratosthenes();
    int n = 21;
    cout << "Number of almost primes in range 1 to "<<n << " is: " << countAlmostPrime(n);
}

実行結果

Number of almost primes in range 1 to 21 is: 8

アルゴリズムのポイント

• 事前計算： エラトステネスの篩により、配列 prime[] に各数が素数かどうかの情報を格納します。これにより素数判定をO(1)で行えます。
• 約数ペアの走査： 各数 i に対し、2から√i までの約数 j を調べます。j が素数ならカウントし、対応する約数 i / j も素数であれば同様にカウントします。
• 平方数への対応： j × j = i の場合（完全平方数）、同じ素因数を二重に数えないよう注意しています。これにより「異なる」素因数の個数を正しく取得できます。
• 判定： 素因数のカウントがちょうど2になった数のみを結果に加算します。

なお、N = 21 の場合、該当するのは 6, 10, 12, 14, 15, 18, 20, 21 の8個です。例えば 12 = 2² × 3 のように、べき乗を含んでいても異なる素因数が2種類であれば準素数として扱われます。