C++を使用してサブアレイ内の素数の数を見つける

この記事では、サブアレイ内の素数の数を見つける方法について説明します。範囲{l、R}を表す2つの整数を持つ正の数arr []およびqクエリの配列があり、指定された範囲内の素数の数を見つける必要があります。以下は、与えられた問題の例です-

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}.

解決策を見つけるためのアプローチ

この状況では、2つのアプローチが思い浮かびます-

ブルートフォース

このアプローチでは、範囲を取得して、その範囲に存在する素数の数を見つけることができます。

例

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

出力

2

ただし、このアプローチの全体的な複雑さは O（Q * N *√N）であるため、このアプローチはあまり良くありません。 、これはあまり良くありません。

効率的なアプローチ

このアプローチでは、Sieve Of Eratosthenesを使用して、要素が素数であるかどうかを示すブール配列を作成し、指定された範囲を調べて、ブール配列から素数の総数を見つけます。

例

#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）であるため、以前に適用したブルートフォースアプローチよりもはるかに高速です。 これは、以前の複雑さよりもはるかに優れています。

このアプローチでは、要素を事前に計算し、素数であるかどうかにフラグを立てます。したがって、これにより複雑さが軽減されます。その上で、Sieve Of Eratosthenesも使用しています。これにより、素数をすばやく見つけることができます。この方法では、 O（N * log（log（N）））ですべての数値に素数または素数でないフラグを付けます。 素因数を使用して数値にフラグを立てることによる複雑さ。

結論

この記事では、エラトステネスのふるいを使用して、O（Q * N）のサブアレイ内の素数を見つけるための問題を解決します。また、この問題のC ++プログラムと、この問題を解決するための完全なアプローチ（通常および効率的）についても学びました。同じプログラムをC、Java、Python、その他の言語などの他の言語で作成できます。