อัลกอริทึมหาจำนวนเฉพาะที่เร็วที่สุดใน C++: Sieve of Eratosthenes

ภาพรวม

Sieve of Eratosthenes (ถังเอราโทสเธนีส) เป็นอัลกอริทึมที่มีประสิทธิภาพสูงสุดสำหรับการหาจำนวนเฉพาะทั้งหมดที่น้อยกว่า n เมื่อ n < 10 ล้าน ประมาณ ความซับซ้อนด้านเวลา O(n log log n) เร็วกว่าการตรวจสอบแต่ละตัว O(n√n) มาก

หลักการทำงาน

1. สร้าง Boolean Array isPrime[0...n] เริ่มต้นทั้งหมด = true
2. ตั้ง isPrime[0] = isPrime[1] = false
3. วน i = 2 ถึง √n:
   • ถ้า isPrime[i] ยังเป็น true → i เป็นจำนวนเฉพาะ
   • ทำเครื่องหมาย false ให้ทุก Multiple ของ i (เริ่มจาก i×i)
4. ค่าที่เหลือเป็น true = จำนวนเฉพาะ

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

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

void sieveOfEratosthenes(int n) {
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false;
    
    int limit = static_cast<int>(sqrt(n));
    for (int i = 2; i <= limit; i++) {
        if (isPrime[i]) {
            // เริ่มจาก i*i เพราะตัวกู่อาจถูกทำเครื่องหมายแล้ว
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    
    cout << "Prime numbers up to " << n << ": ";
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) cout << i << " ";
    }
    cout << "\n";
}

int main() {
    int n;
    cout << "Enter upper limit: ";
    cin >> n;
    sieveOfEratosthenes(n);
    return 0;
}

ผลลัพธ์ตัวอย่าง

Enter upper limit: 15
Prime numbers up to 15: 2 3 5 7 11 13

การเพิ่มประสิทธิภาพ (Optimizations)

1. Bit-Packed Sieve (ลด Memory 8x)

// ใช้ vector<unsigned char> หรือ bitset แทน vector<bool>
// vector<bool> เป็น specialization ที่บีบอัดเป็น 1 bit แล้ว
// แต่ Manual Bit-Packing เร็วกว่าสำหรับ Cache
vector<uint8_t> sieve((n >> 3) + 1, 0xFF);  // 1 bit ต่อจำนวน

2. Wheel Factorization (ข้าม Even Numbers)

// เก็บเฉพาะ Odd Numbers: index i แทนเลข 2*i+1
// ลด Memory และ Operations เหลือครึ่ง
int size = (n - 1) / 2;
vector<bool> isPrime(size, true);
for (int i = 1; i * (2*i + 2) <= n; i++) {  // i=1 → 3
    if (isPrime[i]) {
        int p = 2*i + 1;
        for (int j = (p*p - 1)/2; j < size; j += p) {
            isPrime[j] = false;
        }
    }
}

3. Segmented Sieve (สำหรับ n ใหญ่มาก > 10^9)

• แบ่งช่วง [0, n] เป็น Segments ขนาด √n
• หา Primes ≤ √n ด้วย Sieve ปกติ
• ประมวลผลแต่ละ Segment แยกกัน
• Memory O(√n) แทน O(n)

การเปรียบเทียบประสิทธิภาพ

ข้อสังเกต

• โค้ดต้นฉบับใช้ <bits/stdc++.h> (GCC Extension) → เปลี่ยนเป็น Standard Headers
• memset บน vector<bool> ไม่ได้ → ใช้ Constructor หรือ fill
• Loop Condition: i*i <= n ป้องกัน Overflow ดีกว่า i <= sqrt(n)
• สำหรับ Production ใช้ Library เช่น primesieve (Fastest Known)