C++で1からnまでの素数の合計を求めるプログラムの作り方

この問題では、ある数値 n が与えられます。私たちのタスクは、「1から n までの素数の合計を求めるC++プログラム」を作成することです。

素数とは、約数が「1」と「その数自身」の2つしか存在しない数のことです。たとえば、2、3、5、7 などが素数にあたります。

例を使って問題を理解しましょう。

入力

n = 15

出力

41

説明

1から15までの素数は、2, 3, 5, 7, 11, 13 の6つです。これらをすべて足し合わせると、合計は 41 になります。

解法1：ループで素数を判定するシンプルな方法

最も基本的な解き方は、2から n までの各数値について「その数が素数かどうか」を順番に判定し、素数であれば合計に加算していく方法です。

ある数 i が素数かどうかを判定するには、2 から i/2 までの整数で割り切れるものが存在するかを確認します。1つでも割り切れる数が見つかれば、その数は素数ではありません。

この解法の動作を示すサンプルプログラム

#include <iostream>
using namespace std;

bool isPrime(int n){
    if(n < 2)
        return false;
    for(int i = 2; i <= n/2; i++){
        if(n % i == 0){
            return false;
        }
    }
    return true;
}

int findPrimeSum(int n){
    int sumVal = 0;
    for(int i = 2; i <= n; i++){
        if(isPrime(i))
            sumVal += i;
    }
    return sumVal;
}

int main(){
    int n = 15;
    cout << "1から" << n << "までの素数の合計は " << findPrimeSum(n) << " です";
    return 0;
}

実行結果

1から15までの素数の合計は 41 です

解法2：エラトステネスの篩を使った効率的な方法

より効率的な解法として、エラトステネスの篩（ふるい）を使う方法があります。これは、各素数の倍数を順番にふるい落としていくことで、1から n までのすべての素数を高速に見つけ出す古典的なアルゴリズムです。

計算量は O(n log log n) となり、数値ごとに素数判定を繰り返す解法1（O(n√n) 程度）に比べて、n が大きい場合に大幅に高速に動作します。

この解法の動作を示すサンプルプログラム

#include <iostream>
#include <vector>
using namespace std;

int findPrimeSum(int n){
    vector<bool> isComposite(n + 1, false);
    for(int i = 2; i * i <= n; i++){
        if(!isComposite[i]){
            for(int j = i * i; j <= n; j += i){
                isComposite[j] = true;
            }
        }
    }
    int sumVal = 0;
    for(int i = 2; i <= n; i++){
        if(!isComposite[i])
            sumVal += i;
    }
    return sumVal;
}

int main(){
    int n = 15;
    cout << "1から" << n << "までの素数の合計は " << findPrimeSum(n) << " です";
    return 0;
}

実行結果

1から15までの素数の合計は 41 です

まとめ

1から n までの素数の合計を求めるには、主に次の2つのアプローチがあります。

• 全数チェック方式：各数値を個別に素数判定するシンプルな方法。実装が容易ですが、n が大きくなると処理に時間がかかります。
• エラトステネスの篩：素数を一括で求める効率的なアルゴリズム。大きな n に対しても高速に動作するため、競技プログラミングや実務ではこちらが推奨されます。

入力の規模や要件に応じてこれらの方法を使い分けることで、効率的に素数の合計を計算できます。