ค้นหาจำนวนคู่หลักในอาร์เรย์โดยใช้ C++

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

Input : arr[ ] = { 1, 2, 3, 5, 7, 9 }

Output : 6

From the given array, prime pairs are
(2, 3), (2, 5), (2, 7), (3, 5), (3, 7), (5, 7)

Input : arr[] = {1, 4, 5, 9, 11}

Output : 1

แนวทางในการหาแนวทางแก้ไข

แนวทางกำลังเดรัจฉาน

ตอนนี้เราจะหารือเกี่ยวกับแนวทางพื้นฐานที่สุด นั่นคือแนวทาง 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]); // size of our array.
    int answer = 0; // counter variable to count the number of prime pairs.
    int MAX = INT_MIN; // Max element
    for(int i = 0; i < n; i++){
       MAX = max(MAX, arr[i]);
    }
    bool prime[n]; // boolean array that tells if the element is prime or not.
    memset(prime, false, sizeof(prime)); // initializing all the elements with value of 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

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

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

แนวทางที่มีประสิทธิภาพ

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

ตัวอย่าง

#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]); // size of our array.
   int answer = 0; // counter variable to count the number of prime pairs.
   int MAX = INT_MIN; // Max element
   for(int i = 0; i < n; i++){
       MAX = max(MAX, arr[i]);
   }
   bool prime[n]; // boolean array that tells if the element is prime or not.
   memset(prime, false, sizeof(prime)); // initializing all the elements with value of 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 เพื่อทำเครื่องหมายจำนวนเฉพาะทั้งหมดจนถึงองค์ประกอบ Max ที่เรามีในอาร์เรย์ ในอาร์เรย์บูลอื่น เราใช้ดัชนีอย่างชาญฉลาดในการทำเครื่องหมายองค์ประกอบหากเป็นจำนวนเฉพาะหรือไม่

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

บทสรุป

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