หาจำนวนคู่จำนวนเฉพาะ (Prime Pairs) ในอาร์เรย์ด้วย C++

ในบทความนี้ เราจะอธิบายทุกอย่างเกี่ยวกับการหาจำนวนคู่จำนวนเฉพาะในอาร์เรย์ด้วย C++ เรามีอาร์เรย์ arr[] ของจำนวนเต็ม และเราต้องหาคู่จำนวนเฉพาะที่เป็นไปได้ทั้งหมดที่มีอยู่ในอาร์เรย์ ตัวอย่าง:

Input : arr[ ] = { 1, 2, 3, 5, 7, 9 } Output : 6 จากอาร์เรย์ที่กำหนด คู่จำนวนเฉพาะคือ (2, 3), (2, 5), (2, 7), (3, 5), (3, 7), (5, 7)
Input : arr[] = {1, 4, 5, 9, 11} Output : 1

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

1. วิธี Brute Force

ตอนนี้เราจะอภิปรายวิธีพื้นฐานที่สุด คือ วิธี Brute Force และลองหาอีกวิธีหนึ่ง เพราะวิธีนี้ไม่ค่อยมีประสิทธิภาพ

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

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

void seiveOfEratosthenes(int *arr, bool *prime, int n, int MAX) {
    bool p[MAX+1];
    memset(p, true, sizeof(p));
    p[1] = false;
    p[0] = false;
    for(int i = 2; i * i <= MAX; i++) {
        if(p[i] == true) {
            for(int j = i*2; j <= MAX; j += i) {
                p[j] = false;
            }
        }
    }
    for(int i = 0; i < n; i++) {
        if(p[arr[i]] == true)
            prime[i] = true;
    }
}

int main() {
    int arr[] = {1, 2, 3, 5, 7, 8, 9};
    int n = sizeof(arr) / sizeof(arr[0]); // ขนาดอาร์เรย์
    int answer = 0; // ตัวนับจำนวนคู่จำนวนเฉพาะ
    int MAX = INT_MIN; // สมาชิกสูงสุด
    for(int i = 0; i < n; i++) {
        MAX = max(MAX, arr[i]);
    }
    bool prime[n]; // อาร์เรย์บูลีนบอกว่าสมาชิกเป็นเฉพาะหรือไม่
    memset(prime, false, sizeof(prime)); // เริ่มต้นทุกสมาชิกเป็น false
    seiveOfEratosthenes(arr, prime, n, MAX);
    
    for(int i = 0; i < n-1; i++) {
        for(int j = i+1; j < n; j++) {
            if(prime[i] == true && prime[j] == true)
                answer++;
        }
    }
    cout << answer << "\n";
    return 0;
}

ผลลัพธ์

6

ในวิธีนี้ เราสร้างอาร์เรย์บูลีนที่จะบอกเราว่าสมาชิกไหนเป็นจำนวนเฉพาะ และจากนั้นเราจะวนลูปผ่านคู่ที่เป็นไปได้ทั้งหมด และตรวจสอบว่าตัวเลขทั้งสองในคู่เป็นจำนวนเฉพาะหรือไม่ หากเป็น ให้เพิ่มคำตอบขึ้น 1 และดำเนินต่อไป

แต่วิธีนี้ไม่ค่อยมีประสิทธิภาพ เพราะความซับซ้อนด้านเวลาคือ O(N²) โดย N คือขนาดของอาร์เรย์ของเรา ดังนั้น เราจะทำให้วิธีนี้เร็วขึ้น

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

ในวิธีนี้ โค้ดส่วนใหญ่จะเหมือนเดิม แต่การเปลี่ยนแปลงสำคัญคือ แทนที่จะวนลูปผ่านคู่ที่เป็นไปได้ทั้งหมด เราจะคำนวณจำนวนคู่โดยใช้สูตร

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

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

void seiveOfEratosthenes(int *arr, bool *prime, int n, int MAX) {
    bool p[MAX+1];
    memset(p, true, sizeof(p));
    p[1] = false;
    p[0] = false;
    for(int i = 2; i * i <= MAX; i++) {
        if(p[i] == true) {
            for(int j = i*2; j <= MAX; j += i) {
                p[j] = false;
            }
        }
    }
    for(int i = 0; i < n; i++) {
        if(p[arr[i]] == true)
            prime[i] = true;
    }
}

int main() {
    int arr[] = {1, 2, 3, 5, 7, 8, 9};
    int n = sizeof(arr) / sizeof(arr[0]); // ขนาดอาร์เรย์
    int answer = 0; // ตัวนับจำนวนคู่จำนวนเฉพาะ
    int MAX = INT_MIN; // สมาชิกสูงสุด
    for(int i = 0; i < n; i++) {
        MAX = max(MAX, arr[i]);
    }
    bool prime[n]; // อาร์เรย์บูลีนบอกว่าสมาชิกเป็นเฉพาะหรือไม่
    memset(prime, false, sizeof(prime)); // เริ่มต้นทุกสมาชิกเป็น false
    seiveOfEratosthenes(arr, prime, n, MAX);
    
    for(int i = 0; i < n; i++) {
        if(prime[i] == true)
            answer++;
    }
    answer = (answer * (answer - 1)) / 2;
    cout << answer << "\n";
    return 0;
}

ผลลัพธ์

6

เห็นได้ว่า โค้ดส่วนใหญ่เหมือนวิธีก่อนหน้า แต่การเปลี่ยนแปลงสำคัญที่ลดความซับซ้อนมากคือ สูตรที่เราใช้ คือ n(n-1)/2 ซึ่งจะคำนวณจำนวนคู่จำนวนเฉพาะของเรา

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

ในโค้ดนี้ เราใช้ Sieve of Eratosthenes ทำเครื่องหมายจำนวนเฉพาะทั้งหมดจนถึงสมาชิกสูงสุดที่เรามีในอาร์เรย์ ในอาร์เรย์บูลีนอีกอันหนึ่ง เราทำเครื่องหมายตามดัชนี (index-wise) ว่าสมาชิกเป็นเฉพาะหรือไม่

สุดท้าย เราวนลูปผ่านอาร์เรย์ทั้งหมด หาจำนวนเฉพาะทั้งหมดที่มีอยู่ และหาคู่ที่เป็นไปได้ทั้งหมดโดยใช้สูตร n*(n-1)/2 ด้วยสูตรนี้ ความซับซ้อนของเราลดเหลือ O(N) โดยที่ N คือขนาดของอาร์เรย์ของเรา

สรุป

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