使用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&#39;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)，這不是很好。

高效方法

在這種方法中，我們將使用埃拉托斯特尼篩選法建立一個布林數組，告訴我們該元素是否是素數，然後遍歷給定的範圍並找出該數組中素數的總數。布爾數組。

範例

#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;
}

輸出

2

上述程式碼的解釋

這種方法比我們之前應用的蠻力方法要快得多，因為現在的時間複雜度是O(Q*N)，也就是比以前的複雜度好得多。

在這種方法中，我們預先計算元素並將它們標記為素數或非素數；因此，這降低了我們的複雜性。除此之外，我們也使用埃拉托斯特尼篩法，這將有助於我們更快找到質數。在此方法中，我們透過使用素數因子標記數字，以 O(N*log(log(N))) 複雜度將所有數字標記為質數或非質數。

結論

在本文中，我們解決了使用埃拉托斯特尼篩選法在 O(Q*N) 中尋找子數組中素數數量的問題。我們也學習了解決這個問題的C 程序以及解決這個問題的完整方法（正常且有效率）。我們可以用其他語言寫相同的程序，例如C、java、python等語言。

以上是使用C++編寫，找出子數組中的質數數的詳細內容。更多資訊請關注PHP中文網其他相關文章！