使用 C++ 查找子数组中的质数数
在本文中，我们将描述在子数组中查找素数个数的方法。我们有一个正数数组arr[]和q查询，其中有两个整数表示我们的范围{l,R}我们需要找到给定范围内的素数数量。所以下面是给定问题的一个例子-
Input : arr[] = {1, 2, 3, 4, 5, 6}, q = 1, L = 0, R = 3
Output : 2
In the given range the primes are {2, 3}.
Input : arr[] = {2, 3, 5, 8 ,12, 11}, q = 1, L = 0, R = 5
Output : 4
In the given range the primes are {2, 3, 5, 11}.寻找解决方案的方法
在这种情况下，想到了两种方法-
蛮力
在这种方法中，我们可以获取范围并找到该范围内存在的素数数量。
示例
#include <bits/stdc++.h>
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){ //因为偶数不能是素数，所以我们将i增加2。
if (N % i == 0)
return false; //如果N可以被任何数整除，则它不是素数。
}
return true;
}
int main(){
int N = 6; //数组的大小。
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++; //计数器变量。
}
cout << cnt << "\n";
}
return 0;
}输出结果2
然而，这种方法不是很好，因为这种方法的整体复杂度是O(Q*N*√N)，这不是很好。
有效的方法
在这种方法中，我们将使用SieveOfEratosthenes制作一个布尔数组，告诉我们元素是否为素数，然后遍历给定的范围并从bool数组中找到素数的总数。
示例
#include <bits/stdc++.h>
using namespace std;
vector<bool> sieveOfEratosthenes(int *arr, int n, int MAX){
vector<bool> 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++) {
//如果prime[p]没有改变，那么
//这是一个素数
if (Prime[p] == true) {
//更新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<bool> isprime = sieveOfEratosthenes(arr, n, MAX); //布尔数组。
int q = 1;
while(q--){
int L = 0, R = 3;
int cnt = 0; //数数
for(int i = L; i <= R; i++){
if(isprime[i])
cnt++;
}
cout << cnt << "\n";
}
return 0;
}输出结果2
以上代码说明
这种方法比我们之前应用的蛮力方法快得多，因为现在时间复杂度为O(Q*N)，这比以前的复杂度要好得多。
在这种方法中，我们预先计算元素并将它们标记为素数与否；因此，这降低了我们的复杂性。除此之外，我们还使用了SieveOfEratosthenes，这将帮助我们更快地找到素数。在这种方法中，我们通过使用质因数标记数字来将所有数字标记为O(N*log(log(N)))复杂度中的质数或非质数。
结论
在本文中，我们使用SieveOfEratosthenes解决了在O(Q*N)中找到子数组中素数数的问题。我们还学习了针对这个问题的C++程序以及我们解决这个问题的完整方法（正常和高效）。我们可以用其他语言编写相同的程序，例如C、java、python和其他语言。