Tổng số nguyên tố từ 1 đến n trong C++

Tính tổng các số nguyên tố trong khoảng [1, n].

Ví dụ

n = 15: Số nguyên tố: 2, 3, 5, 7, 11, 13 → Tổng = 41.

Cách 1: Kiểm tra từng số (O(n√n))

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

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

Cách 2: Sàng Eratosthenes (O(n log log n))

Hiệu quả cho n lớn (≤ 10^7).

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

Cài đặt đầy đủ (Sàng)

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

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

int main() {
    int n = 15;
    cout << "Tong so nguyen to tu 1 den " << n << " la " << findPrimeSum(n);
    return 0;
}

Output

Tong so nguyen to tu 1 den 15 la 41

So sánh