阅读 101

使用 C++ 查找数组中的质数对数

在本文中,我们将解释有关使用 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 <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]); // 我们数组的大小。    int answer = 0; // counter 变量来计算素数对的数量。    int MAX = INT_MIN; // 最大元素    for(int i = 0; i < n; i++){
       MAX = max(MAX, arr[i]);
    }
    bool prime[n]; // 判断元素是否为素数的布尔数组。    memset(prime, false, sizeof(prime)); // 用 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


在这种方法中,我们制作了一个 bool 数组,它会告诉我们任何元素是否为质数,然后我们将遍历所有可能的对并检查对中的两个数字是否都是质数。如果是素数,则将答案加一并继续。

但是这种方法不是很有效,因为它的时间复杂度是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]); // 我们数组的大小。   int answer = 0; // counter 变量来计算素数对的数量。   int MAX = INT_MIN; // 最大元素   for(int i = 0; i < n; i++){
       MAX = max(MAX, arr[i]);
   }
   bool prime[n]; // 判断元素是否为素数的布尔数组。   memset(prime, false, sizeof(prime)); // 用 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,它将计算我们的数量素数对。

以上代码说明

在这段代码中,我们使用埃拉托色尼筛法来标记所有素数,直到数组中的 Max 元素。在另一个 bool 数组中,我们按索引标记元素是否为素数。

最后,我们遍历整个数组,找到存在的素数总数,并使用公式 n*(n-1)/2 找到所有可能的对。使用这个公式,我们的复杂度降低到,其中 N 是我们数组的大小。 O(N)

结论

在本文中,我们解决了一个问题,以找出O(n)时间复杂度数组中存在的素数对的数量。我们还学习了针对这个问题的 C++ 程序以及我们解决这个问题的完整方法(正常和高效)。我们可以用其他语言编写相同的程序,例如 C、java、python 和其他语言。


文章分类
百科问答
版权声明:本站是系统测试站点,无实际运营。本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 XXXXXXo@163.com 举报,一经查实,本站将立刻删除。
相关推荐