
在本文中,我们将描述查找子数组中素数数量的方法。我们有一个正数数组 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>
using namespace std;
bool isPrime(int N){
if (N <h2>输出</h2>
<pre class="brush:php;toolbar:false;">2
但是,这种方法并不是很好,因为这种方法的整体复杂度是O(Q*N*√N),这不是很好。
高效方法
在这种方法中,我们将使用埃拉托斯特尼筛法创建一个布尔数组,告诉我们该元素是否是素数,然后遍历给定的范围并找到该数组中素数的总数。布尔数组。
示例
#include <bits>
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 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 <h2>输出</h2>
<pre class="brush:php;toolbar:false;">2
上述代码的解释
这种方法比我们之前应用的蛮力方法要快得多,因为现在的时间复杂度是O(Q*N),即比以前的复杂性要好得多。
在这种方法中,我们预先计算元素并将它们标记为素数或非素数;因此,这降低了我们的复杂性。除此之外,我们还使用埃拉托斯特尼筛法,这将帮助我们更快地找到素数。在此方法中,我们通过使用素数因子标记数字,以 O(N*log(log(N))) 复杂度将所有数字标记为素数或非素数。
结论
在本文中,我们解决了使用埃拉托斯特尼筛法在 O(Q*N) 中查找子数组中素数数量的问题。我们还学习了解决这个问题的C++程序以及解决这个问题的完整方法(正常且高效)。我们可以用其他语言编写相同的程序,例如C、java、python等语言。
C++免费学习笔记(深入):立即使用
在学习笔记中,你将探索 C++ 的入门与实战技巧!











