C++ で書かれており、部分配列内の素数の数を見つけます。

この記事では、部分配列内の素数の数を求める方法について説明します。正の数の配列 arr[] と、範囲 {l, R} を表す 2 つの整数を含む 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&#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 中国語 Web サイトの他の関連記事を参照してください。