C++で最小の素因数が指定した素数となる10^6未満の数を数える方法

ある素数 num が与えられたとき、最小の素因数が num と一致するような 10⁶ 未満のすべての数の個数を求めるのがこの記事のテーマです。

この問題は、エラトステネスのふるいを少し工夫するだけで効率的に解くことができます。通常のふるいは素数を列挙するために使われますが、合成数に初めて「素数ではない」という印を付ける際に使用した素数こそが、その数の最小の素因数に相当します。この性質を利用すれば、各素数を最小の素因数に持つ数の個数を一度に集計できます。

例

入力 − num = 7
出力 − 該当する数の個数 = 38095

入力 − num = 3
出力 − 該当する数の個数 = 166667

アルゴリズムの手順

• 対象となる素数 num を入力として受け取ります。

• i を 2 から始め、i が最大値（MAX）以下である間、i を 1 ずつ増やしながらループを回します。

• ループ内で、s_prime[i] が 0 であるかどうか（i が素数であるかどうか）を確認します。

• 内側のループを作成します。j を i × 2 に設定し、j が MAX 以下である間、j を j + i ずつ増やしていきます。

• このとき s_prime[j] が 0 のままなら、i が j の最小の素因数であることを意味します。

• s_prime[j] に 1 を代入し、j を合成数としてマークします。

• s_count[i] を 1 増やして、「最小の素因数が i である数」の個数をカウントします。

• 最後に結果を出力します。なお、素数 num 自身も「最小の素因数が num である数」に該当するため、答えには 1 を加算します。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
#define MAX 1000000
// 素数判定用のふるいと
// 最小素因数ごとの個数を格納する配列
int s_prime[MAX + 4] = { 0 }, s_count[MAX + 4] = { 0 };
void create_sieve(){
    // 1 は素数ではない
    s_prime[1] = 1;
    // ふるいを作成
    for (int i = 2; i <= MAX; i++){
        // i が素数の場合
        if (s_prime[i] == 0){
            for (int j = i * 2; j <= MAX; j += i){
                // i が最小の素因数である場合
                if (s_prime[j] == 0){
                    // j は素数ではない
                    s_prime[j] = 1;
                    // 最小の素因数が i となる数をカウント
                    s_count[i]++;
                }
            }
        }
    }
}
int main(){
    // ふるいを作成
    create_sieve();
    int N = 7;
    cout << "Number of prime factors = " << (s_count[N] + 1) << endl;
    N = 3;
    cout << "Number of prime factors = " << (s_count[N] + 1) << endl;
    return 0;
}

出力

上記のコードを実行すると、次のような出力が得られます −

Number of prime factors = 38095
Number of prime factors = 166667