在本文中，我們將解釋有關使用 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現在我們將討論最基本的方法，即暴力方法，並嘗試找到另一種方法：這種方法效率不高。
#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，它將計算我們的素數對的數量。
在這段程式碼中，我們使用埃拉托斯特尼篩法來標記所有質數，直到我們在大批。在另一個布林數組中，我們按索引標記元素是否為素數。
最後，我們遍歷整個數組，找到存在的質數總數，並找到所有可能的素數使用公式 n*(n-1)/2 進行配對。透過這個公式，我們的複雜度降低到 O(N)，其中 N 是陣列的大小。
在本文中，我們解決一個問題，以 O(n) 的時間複雜度找出陣列中存在的質數對的數量。我們也學習了解決這個問題的C 程序以及解決這個問題的完整方法（正常且有效率）。我們可以用其他語言寫相同的程序，例如C、java、python等語言。
以上是使用C++編寫，找出數組中的質數對數量的詳細內容。更多資訊請關注PHP中文網其他相關文章！
