在本文中，我们将描述查找子数组中素数数量的方法。我们有一个正数数组 arr[] 和 q 个查询，其中有两个整数表示我们的范围 {l, R}，我们需要找到给定范围内的素数数量。下面是给定问题的示例 –
Input : arr[] = {1, 2, 3, 4, 5, 6}, q = 1, L = 0, R = 3Output : 2In the given range the primes are {2, 3}.Input : arr[] = {2, 3, 5, 8 ,12, 11}, q = 1, L = 0, R = 5Output : 4In the given range the primes are {2, 3, 5, 11}.
寻找解决方案的方法
在这种情况下，我想到了两种方法 –
暴力破解
在这种方法中，我们可以采用范围并找出该范围内存在的素数数量。
示例
#include using namespace std;bool isPrime(int N){ if (N <= 1) return false; if (N <= 3) return true; if(N % 2 == 0 || N % 3 == 0) return false; for (int i = 5; i * i <= N; i = i + 2){ // as even number can't be prime so we increment i by 2. if (N % i == 0) return false; // if N is divisible by any number then it is not prime. } return true;}int main(){ int N = 6; // size of array. int arr[N] = {1, 2, 3, 4, 5, 6}; int Q = 1; while(Q--){ int L = 0, R = 3; int cnt = 0; for(int i = L; i <= R; i++){ if(isPrime(arr[i])) cnt++; // counter variable. } cout << cnt << "n"; } return 0;}
输出
2
但是，这种方法并不是很好，因为这种方法的整体复杂度是O(Q*N*√N)，这不是很好。
立即学习“C++免费学习笔记（深入）”；
高效方法
在这种方法中，我们将使用埃拉托斯特尼筛法创建一个布尔数组，告诉我们该元素是否是素数，然后遍历给定的范围并找到该数组中素数的总数。布尔数组。
示例
#include using namespace std;vector sieveOfEratosthenes(int *arr, int n, int MAX){ vector p(n); bool Prime[MAX + 1]; for(int i = 2; i < MAX; i++) Prime[i] = true; Prime[1] = false; for (int p = 2; p * p <= MAX; p++) { // If prime[p] is not changed, then // it is a prime if (Prime[p] == true) { // Update all multiples of p for (int i = p * 2; i <= MAX; i += p) Prime[i] = false; } } for(int i = 0; i < n; i++){ if(Prime[arr[i]]) p[i] = true; else p[i] = false; } return p;}int main(){ int n = 6; int arr[n] = {1, 2, 3, 4, 5, 6}; int MAX = -1; for(int i = 0; i < n; i++){ MAX = max(MAX, arr[i]); } vector isprime = sieveOfEratosthenes(arr, n, MAX); // boolean array. int q = 1; while(q--){ int L = 0, R = 3; int cnt = 0; // count for(int i = L; i <= R; i++){ if(isprime[i]) cnt++; } cout << cnt << "n"; } return 0;}
输出
2
上述代码的解释
这种方法比我们之前应用的蛮力方法要快得多，因为现在的时间复杂度是O(Q*N)，即比以前的复杂性要好得多。
在这种方法中，我们预先计算元素并将它们标记为素数或非素数；因此，这降低了我们的复杂性。除此之外，我们还使用埃拉托斯特尼筛法，这将帮助我们更快地找到素数。在此方法中，我们通过使用素数因子标记数字，以 O(N*log(log(N))) 复杂度将所有数字标记为素数或非素数。
结论
在本文中，我们解决了使用埃拉托斯特尼筛法在 O(Q*N) 中查找子数组中素数数量的问题。我们还学习了解决这个问题的C++程序以及解决这个问题的完整方法（正常且高效）。我们可以用其他语言编写相同的程序，例如C、java、python等语言。
以上就是使用C++编写，找到子数组中的质数数量的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1444198.html
微信扫一扫 
支付宝扫一扫 
