Trong bài này, chúng tôi sẽ mô tả các cách để tìm số nguyên tố trong một mảng con. Chúng ta có một mảng các số dương arr [] và q truy vấn có hai số nguyên biểu thị phạm vi {l, R} của chúng tôi, chúng tôi cần tìm số nguyên tố trong phạm vi đã cho. Vì vậy, dưới đây là một ví dụ về vấn đề đã cho -
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}. Phương pháp tiếp cận để tìm giải pháp
Trong tình huống này, có hai cách tiếp cận được nghĩ đến -
Lực lượng vũ phu
Theo cách tiếp cận này, chúng ta có thể lấy phạm vi và tìm số lượng số nguyên tố có trong phạm vi đó.
Ví dụ
#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;
} Đầu ra
2
Tuy nhiên, cách tiếp cận này không tốt lắm vì độ phức tạp tổng thể của cách tiếp cận này là O (Q * N * √N) , điều này không tốt lắm.
Phương pháp tiếp cận hiệu quả
Trong cách tiếp cận này, chúng ta sẽ sử dụng Sieve Of Eratosthenes để tạo một mảng boolean cho chúng ta biết liệu phần tử có phải là số nguyên tố hay không, sau đó đi qua phạm vi đã cho và tìm tổng số số nguyên tố từ mảng bool.
Ví dụ
#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;
} Đầu ra
2
Giải thích về Quy tắc trên
Cách tiếp cận này nhanh hơn nhiều so với cách tiếp cận Brute Force mà chúng tôi đã áp dụng trước đó vì độ phức tạp về thời gian là O (Q * N) tốt hơn nhiều so với độ phức tạp trước đây.
Trong cách tiếp cận này, chúng tôi tính toán trước các phần tử và gắn cờ chúng là nguyên tố hay không; do đó, điều này làm giảm sự phức tạp của chúng tôi. Trên đó, chúng tôi cũng đang sử dụng Sieve Of Eratosthenes, sẽ giúp chúng tôi tìm số nguyên tố nhanh hơn. Trong phương pháp này, chúng tôi gắn cờ tất cả các số là số nguyên tố hoặc không phải số nguyên tố trong O (N * log (log (N))) độ phức tạp bằng cách gắn cờ các số bằng cách sử dụng các thừa số nguyên tố của chúng.
Kết luận
Trong bài viết này, chúng tôi giải quyết một vấn đề để tìm Số nguyên tố trong một mảng con ở O (Q * N) bằng cách sử dụng Sieve Of Eratosthenes. Chúng tôi cũng đã học chương trình C ++ cho vấn đề này và cách tiếp cận hoàn chỉnh (Bình thường và hiệu quả) mà chúng tôi đã giải quyết vấn đề này. Chúng ta có thể viết cùng một chương trình bằng các ngôn ngữ khác như C, java, python và các ngôn ngữ khác.