在本文中，我们将解释有关使用 C++ 查找数组中素数对数量的所有内容。我们有一个整数数组 arr[]，我们需要找到其中存在的所有可能的素数对。这是问题的示例 –
Input : arr[ ] = { 1, 2, 3, 5, 7, 9 }Output : 6From 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 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是数组的大小，所以现在我们要使这种方法更快。
立即学习“C++免费学习笔记（深入）”；
高效方法
在这种方法中，大部分代码都是相同的，但关键的变化是，我们不再遍历所有可能的配对，而是使用一个公式来计算它们。
示例
#include 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++编写，找到数组中的素数对数量的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1445241.html
微信扫一扫 
支付宝扫一扫 
