이 기사에서는 부분배열에서 소수의 수를 찾는 방법을 설명합니다. 우리는 우리의 범위 {l, R}을 나타내는 두 개의 정수를 갖는 양수 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}. 해결책을 찾기 위한 접근 방식
이 상황에서 두 가지 접근 방식이 떠오릅니다.
브루트 포스
이 접근 방식에서 우리는 범위를 취하고 그 범위에 존재하는 소수의 수를 찾을 수 있습니다.
예시
#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)이므로 이전에 적용한 Brute Force 접근 방식보다 훨씬 빠릅니다. 이전 복잡성보다 훨씬 낫습니다.
이 접근 방식에서는 요소를 미리 계산하고 소수인지 여부에 플래그를 지정합니다. 따라서 복잡성이 줄어듭니다. 그 외에도 소수를 더 빨리 찾는 데 도움이 되는 Sieve Of Eratosthenes도 사용하고 있습니다. 이 방법에서는 O(N*log(log(N)))에서 모든 숫자를 소수 또는 소수가 아닌 것으로 플래그 지정합니다. 소인수를 사용하여 숫자에 플래그를 지정하여 복잡성을 해소합니다.
결론
이 기사에서는 에라토스테네스의 체를 사용하여 O(Q*N)의 하위 배열에서 소수의 수를 찾는 문제를 해결합니다. 우리는 또한 이 문제에 대한 C++ 프로그램과 이 문제를 해결하는 완전한 접근 방식(보통 및 효율적)을 배웠습니다. C, Java, python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다.