使用C++编写，找到子数组中的质数数量-C++-PHP中文网

使用C++编写，找到子数组中的质数数量

王林

发布： 2023-09-01 08:37:06

转载

1285人浏览过

使用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){ // 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;
}

登录后复制

输出

登录后复制

但是，这种方法并不是很好，因为这种方法的整体复杂度是O(Q*N*√N)，这不是很好。

立即学习“C++免费学习笔记（深入）”；

PHP经典实例(第二版)

PHP经典实例（第2版）能够为您节省宝贵的Web开发时间。有了这些针对真实问题的解决方案放在手边，大多数编程难题都会迎刃而解。《PHP经典实例(第2版)》将PHP的特性与经典实例丛书的独特形式组合到一起，足以帮您成功地构建跨浏览器的Web应用程序。在这个修订版中，您可以更加方便地找到各种编程问题的解决方案，《PHP经典实例(第2版)》中内容涵盖了：表单处理；Session管理；数据库交互；使用We

453

查看详情

高效方法

在这种方法中，我们将使用埃拉托斯特尼筛法创建一个布尔数组，告诉我们该元素是否是素数，然后遍历给定的范围并找到该数组中素数的总数。布尔数组。

示例

#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++) {
       // 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<bool> 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;
}

登录后复制