C++で1からnまでの素数の積を求める方法

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

アプローチ：エラトステネスの篩

この問題を効率的に解くには、エラトステネスの篩（ふるい）と呼ばれる古典的なアルゴリズムを使います。この手法では、2 から始めて各素数の倍数を順に除外していくことで、1 から n までのすべての素数を高速に見つけることができます。その後、見つかった素数をすべて掛け合わせれば答えが得られます。

アルゴリズムの手順

1. サイズ n+1 の真偽値配列を作成し、すべて true（素数候補）で初期化します。
2. 2 から √n までの各数値 i について、i が素数なら i の倍数をすべて false にします。
3. 最後に、配列内で true のまま残っている数値（＝素数）をすべて掛け合わせます。

C++での実装例

#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 となり、プログラムの出力と一致します。

エラトステネスの篩の計算量は O(n log log n) であり、単純に各数値について素数判定を繰り返す方法（O(n√n)）よりもはるかに高速です。そのため、n が大きくなっても効率よく動作します。

注意点

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