C++でn以下の素数の積を求める方法【エラトステネスの篩】

はじめに

数値 n が与えられたとき、1 から n までの範囲に含まれる素数の積を求めることを考えてみましょう。例えば n = 7 の場合、2 × 3 × 5 × 7 = 210 となるため、出力は 210 になります。

アルゴリズムの考え方

この問題を解くには、まずエラトステネスの篩（ふるい）を使って 1 から n までのすべての素数を効率よく列挙し、その後、見つかった素数を順番に掛け合わせて積を計算します。

エラトステネスの篩は、各素数の倍数を順次除外していくことで素数を判定する古典的な手法です。計算量が O(n log log n) と非常に効率的なため、ある程度大きな n に対しても高速に動作します。

処理の流れ

1. サイズ n+1 の真偽値配列を用意し、すべて true（素数候補）で初期化します。
2. i を 2 から √n まで走査し、prime[i] が true なら i の倍数をすべて false に設定します。
3. 最後に prime[i] が true になっている i（素数）をすべて掛け合わせて返します。

サンプルコード

#include<iostream>
using namespace std;
long PrimeProds(int n) {
    bool prime[n + 1];
    for(int i = 0; i<=n; i++){
        prime[i] = true;
    }
    for (int i = 2; i * i <= n; i++) {
        if (prime[i] == true) {
            for (int j = i * 2; j <= n; j += i)
                prime[j] = false;
        }
    }
    long product = 1;
    for (int i = 2; i <= n; i++)
        if (prime[i])
            product *= i;
    return product;
}
int main() {
    int n = 8;
    cout << "Product of primes up to " << n << " is: " << PrimeProds(n);
}

実行結果

Product of primes up to 8 is: 210

n = 8 の場合、8 以下の素数は 2、3、5、7 の 4 つなので、その積は 2 × 3 × 5 × 7 = 210 となります。

注意点：オーバーフローに気をつける

素数の積は増加が非常に速いため、n がある程度大きくなると long 型では値を保持できなくなります。より大きな n を扱う場合は、unsigned long long 型を使用するか、多倍長整数ライブラリ（GMP など）の利用を検討してください。