หาจำนวนจำนวนเฉพาะในซับอาร์เรย์ด้วย C++

ในบทความนี้ เราจะอธิบายวิธีการหาจำนวนจำนวนเฉพาะ (prime numbers) ในซับอาร์เรย์ (subarray) เรามีอาร์เรย์ของจำนวนบวก arr[] และ q คิวรี่ (queries) ที่มีสองจำนวนเต็ม แทนช่วง {L, R} เราต้องหาจำนวนจำนวนเฉพาะในช่วงที่กำหนด ตัวอย่าง:

Input : arr[] = {1, 2, 3, 4, 5, 6}, q = 1, L = 0, R = 3 Output : 2 ในช่วงที่กำหนด จำนวนเฉพาะคือ {2, 3}
Input : arr[] = {2, 3, 5, 8, 12, 11}, q = 1, L = 0, R = 5 Output : 4 ในช่วงที่กำหนด จำนวนเฉพาะคือ {2, 3, 5, 11}

วิธีการหาคำตอบ

ในสถานการณ์นี้ มีสองวิธีที่นึกออกมา:

1. วิธี Brute Force

ในวิธีนี้ เราสามารถรับช่วงและหาจำนวนจำนวนเฉพาะที่มีอยู่ในช่วงนั้น

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

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

bool isPrime(int N) {
    if (N <= 1)
        return false;
    if (N <= 3)
        return true;
    if (N % 2 == 0 || N % 3 == 0)
        return false;
    for (int i = 5; i * i <= N; i = i + 2) { // เนื่องจากเลขคู่ไม่เป็นเฉพาะ เราเพิ่ม i ทีละ 2
        if (N % i == 0)
            return false; // หาก N หารด้วยตัวเลขไหนลงตัว แสดงว่าไม่ใช่เฉพาะ
    }
    return true;
}

int main() {
    int N = 6; // ขนาดอาร์เรย์
    int arr[N] = {1, 2, 3, 4, 5, 6};
    int Q = 1;
    while(Q--) {
        int L = 0, R = 3;
        int cnt = 0;
        for(int i = L; i <= R; i++) {
            if(isPrime(arr[i]))
                cnt++; // ตัวนับ
        }
        cout << cnt << "\n";
    }
    return 0;
}

ผลลัพธ์

2

อย่างไรก็ตาม วิธีนี้ไม่ค่อยดี เพราะความซับซ้อนโดยรวมของวิธีนี้คือ O(Q × N × √N) ซึ่งไม่ค่อยดี

2. วิธีที่มีประสิทธิภาพ (Efficient Approach)

ในวิธีนี้ เราจะใช้ Sieve of Eratosthenes (โครงรังเอราโทสเธนีส) เพื่อสร้างอาร์เรย์บูลีน (boolean array) ที่บอกว่าสมาชิกนั้นเป็นจำนวนเฉพาะหรือไม่ แล้ววนลูปผ่านช่วงที่กำหนดและหาจำนวนเฉพาะทั้งหมดจากอาร์เรย์บูลีน

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

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

vector<bool> sieveOfEratosthenes(int *arr, int n, int MAX) {
    vector<bool> p(n);
    bool Prime[MAX + 1];
    for(int i = 2; i < MAX; i++)
        Prime[i] = true;
    Prime[1] = false;
    
    for (int p = 2; p * p <= MAX; p++) {
        // หาก Prime[p] ไม่เปลี่ยนแปลง แสดงว่าเป็นเฉพาะ
        if (Prime[p] == true) {
            // อัปเดตตัวคูณทั้งหมดของ p
            for (int i = p * 2; i <= MAX; i += p)
                Prime[i] = false;
        }
    }
    
    for(int i = 0; i < n; i++) {
        if(Prime[arr[i]])
            p[i] = true;
        else
            p[i] = false;
    }
    return p;
}

int main() {
    int n = 6;
    int arr[n] = {1, 2, 3, 4, 5, 6};
    int MAX = -1;
    for(int i = 0; i < n; i++) {
        MAX = max(MAX, arr[i]);
    }
    
    vector<bool> isprime = sieveOfEratosthenes(arr, n, MAX); // อาร์เรย์บูลีน
    int q = 1;
    while(q--) {
        int L = 0, R = 3;
        int cnt = 0; // count
        for(int i = L; i <= R; i++) {
            if(isprime[i])
                cnt++;
        }
        cout << cnt << "\n";
    }
    return 0;
}

ผลลัพธ์

2

คำอธิบายโค้ด

วิธีนี้เร็วกว่าวิธี Brute Force ที่เราใช้ก่อนหน้านี้มาก เนื่องจากความซับซ้อนด้านเวลาตอนนี้คือ O(Q × N) ซึ่งดีกว่าความซับซ้อนก่อนหน้านี้มาก

ในวิธีนี้ เราคำนวณล่วงหน้า (precompute) สมาชิกและทำเครื่องหมายว่าเป็นเฉพาะหรือไม่ ดังนั้นจึงลดความซับซ้อนของเราลง นอกจากนี้ เรายังใช้ Sieve of Eratosthenes ซึ่งจะช่วยให้เราหาจำนวนเฉพาะได้เร็วขึ้น ในวิธีนี้ เราทำเครื่องหมายตัวเลขทั้งหมดว่าเป็นเฉพาะหรือไม่ใช่เฉพาะในความซับซ้อน O(N × log(log N)) โดยการทำเครื่องหมายตัวเลขโดยใช้ตัวประกอบเฉพาะของมัน

สรุป

ในบทความนี้ เราแก้ปัญหาการหาจำนวนจำนวนเฉพาะในซับอาร์เรย์ ด้วยความซับซ้อน O(Q × N) โดยใช้ Sieve of Eratosthenes เรายังเรียนรู้โปรแกรม C++ สำหรับปัญหานี้ และวิธีการแก้ปัญหาทั้งแบบปกติและแบบมีประสิทธิภาพ สามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, Java, Python ได้เช่นกัน