資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用 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查詢解決方案的方法
暴力方法
現在我們將討論所有方法中最基本的方法，即暴力方法，並嘗試找到另一種方法，因為這種方法效率不高。
示例
#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
在這種方法中，我們正在建立一個布林陣列，它將告訴我們任何元素是否是素數，然後我們遍歷所有可能的對並檢查對中的兩個數字是否都是素數。如果是素數，則將答案加 1 並繼續。
但是這種方法效率不高，因為它的時間複雜度為 **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 和其他語言）編寫相同的程式。
更新於： 2021 年 11 月 24 日
281 次檢視
廣告