Ditulis dalam C++, cari bilangan pasangan nombor perdana dalam tatasusunan

Dalam artikel ini, kami akan menerangkan segala-galanya tentang mencari bilangan pasangan perdana dalam tatasusunan menggunakan C++. Kami mempunyai tatasusunan integer arr[] dan kami perlu mencari semua kemungkinan pasangan nombor perdana yang terdapat di dalamnya. Berikut adalah contoh masalah -

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

Cara mencari penyelesaian

Kaedah brute force

Sekarang kita akan membincangkan kaedah paling asas iaitu kaedah brute force dan cuba cari cara lain: Kaedah ini tidak cekap. Contoh

#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;
}

. Jika ia adalah nombor perdana, tambahkan satu jawapan dan teruskan.

Tetapi kaedah ini tidak begitu cekap kerana kerumitan masanya ialah

O(N*N)

, di mana N ialah saiz tatasusunan, jadi sekarang kami ingin membuat kaedah ini lebih cepat.

Kaedah yang cekap

Dalam kaedah ini, kebanyakan kod adalah sama, tetapi perubahan utama ialah daripada menggelungkan semua pasangan yang mungkin, kami menggunakan formula untuk mengiranya.

Contoh

6

Output

#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;
}

Seperti yang anda lihat, kebanyakan kod adalah sama seperti kaedah sebelumnya, tetapi perubahan utama yang sangat mengurangkan kerumitan adalah formula yang kami gunakan, iaitu n(n-1) /2 , yang akan mengira bilangan pasangan perdana kita.

Penjelasan kod di atas

Dalam kod ini, kami menggunakan Ayak Eratosthenes untuk melabel semua nombor perdana sehingga kami berada dalam kumpulan yang besar. Dalam tatasusunan boolean yang lain, kami menandakan mengikut indeks sama ada elemen itu perdana atau tidak.

Akhir sekali, kami mengulangi keseluruhan tatasusunan, mencari jumlah bilangan prima yang hadir dan mencari semua pasangan prima yang mungkin menggunakan formula n*(n-1)/2. Dengan formula ini, kerumitan kami dikurangkan kepada

O(N)

, dengan N ialah saiz tatasusunan.

Kesimpulan

Dalam artikel ini, kami menyelesaikan masalah untuk mencari bilangan pasangan perdana yang hadir dalam tatasusunan dalam kerumitan masa O(n). Kami juga mempelajari program C++ untuk menyelesaikan masalah ini dan cara lengkap untuk menyelesaikan masalah ini (biasa dan cekap). Kita boleh menulis program yang sama dalam bahasa lain, seperti C, java, python dan bahasa lain.

Atas ialah kandungan terperinci Ditulis dalam C++, cari bilangan pasangan nombor perdana dalam tatasusunan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!