ผลรวมจำนวนเฉพาะระหว่าง 1 ถึง N ใน C++

ภาพรวมปัญหา

หาผลรวมของจำนวนเฉพาะ (prime numbers) ทั้งหมดระหว่าง 1 ถึง n

ตัวอย่าง

n = 15 → เฉพาะ: 2,3,5,7,11,13 → ผลรวม = 41

วิธีแก้ปัญหา 1: ตรวจสอบทีละตัว (O(N√N))

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

วิธีแก้ปัญหา 2: Sieve of Eratosthenes (O(N log log N)) - แนะนำ

สร้างอาเรย์ boolean ขนาด n+1 ตั้งค่า true ทั้งหมด แล้วทำเครื่องหมายตัวประกอบเป็น false

โค้ด C++ (Sieve)

#include <iostream>
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 sumVal = 0;
    for (int i = 2; i <= n; i++)
        if (isPrime[i]) sumVal += i;
    return sumVal;
}

int main() {
    int n = 15;
    cout << "The sum of prime numbers between 1 to " << n << " is " << findPrimeSum(n);
    return 0;
}

ผลลัพธ์

n = 15 → 41

การวิเคราะห์ความซับซ้อน

• เวลา: O(N log log N)
• พื้นที่: O(N)