C++로 작성되어 하위 배열에서 소수의 개수를 찾습니다.

이 글에서는 하위 배열에서 소수의 개수를 구하는 방법을 설명하겠습니다. 양수의 배열 arr[]과 범위 {l, R}을 나타내는 두 개의 정수가 있는 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}.

해결책을 찾는 방법

이 경우에는 두 가지 방법을 생각했습니다. -

Brute force

이 방법에서는 범위를 취하여 소수의 수를 알아낼 수 있습니다. 이 범위에 존재하는 숫자입니다.

Example

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

Output

2

그러나 이 방법의 전체적인 복잡도는 O(Q*N*√N)이므로 그다지 좋지 않습니다.

효율적인 방법

이 방법에서는 에라토스테네스의 체를 사용하여 요소가 소수인지 아닌지 알려주는 부울 배열을 만든 다음 주어진 범위를 반복하여 배열에 있는 전체 소수 수를 찾습니다. . 부울 배열.

Example

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

Output

2

위 코드에 대한 설명

이 방법은 이전에 적용한 무차별 방식보다 훨씬 빠릅니다. 이제 시간 복잡도는 O(Q*N)입니다. 즉, 이전 복잡도보다 훨씬 낫다.

이 방법에서는 요소를 미리 계산하고 소수 또는 비소수로 표시하므로 복잡성이 줄어듭니다. 이 외에도 우리는 소수를 더 빨리 찾는 데 도움이 되는 에라토스테네스의 체(Sieve of Eratosthenes)를 사용하고 있습니다. 이 방법에서는 숫자에 소인수 레이블을 지정하여 모든 숫자에 O(N*log(log(N))) 복잡도를 갖는 소수 또는 비소수로 레이블을 지정합니다.

결론

이 기사에서는 Sieve of Eratosthenes를 사용하여 O(Q*N)의 하위 배열에서 소수 개수를 찾는 문제를 해결했습니다. 우리는 또한 이 문제를 해결하기 위한 C++ 프로그램과 이 문제를 해결하는 완전한 방법(정상적이고 효율적인)을 배웠습니다. C, Java, Python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다.

위 내용은 C++로 작성되어 하위 배열에서 소수의 개수를 찾습니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!