นับจำนวนเฉพาะในช่วง [START, END] ใน C++

ภาพรวมปัญหา

ให้ช่วง START และ END ต้องการนับจำนวนเฉพาะ (prime numbers) ในช่วง [START, END]

ตัวอย่าง

Input: Start=1, End=20

Output: 8

คำอธิบาย: 2, 3, 5, 7, 11, 13, 17, 19

Input: Start=100, End=200

Output: 21

แนวทาง Naive (ตรวจสอบแต่ละตัว)

1. ฟังก์ชัน isprime(int num) ตรวจสอบจำนวนเฉพาะ
2. วนลูป i จาก START ถึง END
3. ถ้า isprime(i) ให้เพิ่ม count

โค้ดตัวอย่าง (Naive)

#include <bits/stdc++.h>
using namespace std;

bool isprime(int num) {
    if (num <= 1) return false;
    for (int i = 2; i * i <= num; i++) { // ปรับปรุง: ตรวจจนถึง sqrt(num)
        if (num % i == 0) return false;
    }
    return true;
}

int countPrimes(int strt, int end) {
    int count = 0;
    for (int i = strt; i <= end; i++) {
        if (isprime(i)) count++;
    }
    return count;
}

int main() {
    int START = 10, END = 20;
    cout << "Primes in Ranges: " << countPrimes(START, END);
    return 0;
}

ผลลัพธ์

Primes in Ranges: 4

แนวทางที่มีประสิทธิภาพมากกว่า (Sieve of Eratosthenes)

สำหรับช่วงใหญ่ (END ≤ 10⁶ หรือ 10⁷) ใช้ Sieve

int countPrimes_sieve(int strt, int end) {
    vector<bool> isPrime(end + 1, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i <= end; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= end; j += i)
                isPrime[j] = false;
        }
    }
    int count = 0;
    for (int i = strt; i <= end; i++)
        if (isPrime[i]) count++;
    return count;
}

Segmented Sieve สำหรับช่วงใหญ่มาก (END ≤ 10¹², END-START ≤ 10⁶)

ใช้ Sieve หาเฉพาะถึง √END แล้วคัดกรองช่วง [START, END]

ความซับซ้อน