इस लेख में हम सबअरे में अभाज्य संख्याओं की संख्या ज्ञात करने के तरीकों का वर्णन करेंगे। हमारे पास सकारात्मक संख्याओं की एक सरणी है arr[] और q दो पूर्णांक वाले प्रश्न जो हमारी सीमा को दर्शाते हैं {l, R} हमें दी गई सीमा में अभाज्य संख्याओं की संख्या ज्ञात करने की आवश्यकता है। तो नीचे दी गई समस्या का एक उदाहरण है -
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) है जो पिछली जटिलता से काफी बेहतर है।
इस दृष्टिकोण में, हम तत्वों की पूर्व-गणना करते हैं और उन्हें प्रमुख के रूप में चिह्नित करते हैं या नहीं; इस प्रकार, यह हमारी जटिलता को कम करता है। इसके अलावा, हम Sieve Of Eratosthenes का भी उपयोग कर रहे हैं, जो हमें अभाज्य संख्याओं को तेज़ी से खोजने में मदद करेगा। इस विधि में, हम O(N*log(log(N))) में सभी नंबरों को अभाज्य या अभाज्य के रूप में चिह्नित करते हैं संख्याओं को उनके अभाज्य गुणनखंडों का उपयोग करके फ़्लैग करके जटिलता।
निष्कर्ष
इस लेख में, हम Sieve Of Eratosthenes का उपयोग करके O(Q*N) में एक सबरे में अभाज्य संख्याओं की संख्या ज्ञात करने के लिए एक समस्या का समाधान करते हैं। हमने इस समस्या के लिए C++ प्रोग्राम और संपूर्ण दृष्टिकोण (सामान्य और कुशल) भी सीखा जिसके द्वारा हमने इस समस्या को हल किया। हम उसी प्रोग्राम को अन्य भाषाओं जैसे C, java, python, और अन्य भाषाओं में लिख सकते हैं।