数据结构
网络
关系数据库管理系统
操作系统
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 次查看
广告