दिए गए समस्या में, हमें दिए गए पूर्णांक n के सभी भाजक प्रिंट करने की आवश्यकता है।
इनपुट: 15 आउटपुट: 1 3 5 15 व्याख्या: 15 के भाजक हैं: 1, 3, 5, 15 इनपुट: 30 आउटपुट: 1 2 3 5 15 30
दिए गए समस्या में, हम n के सभी भाजक खोजने के लिए एराटोस्थनीज की छलनी में उपयोग किए गए दृष्टिकोण को लागू कर सकते हैं।
समाधान का दृष्टिकोण
दिए गए दृष्टिकोण में, हम उस अवधारणा को लागू करेंगे जिस पर एराटोस्थनीज की छलनी आधारित है और n के भाजक खोजेंगे।
उदाहरण
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
vector<int> divisors[100001]; // प्रत्येक संख्या के साथ उसके सभी भाजक रखने वाला वेक्टर
void findsieve(int max) {
// वेक्टर डिवाइजर्स को 10^5 तक डेटा से भरना
for(int i = 1; i <= max; i++) {
for(int j = i; j <= max; j += i)
divisors[j].push_back(i);
}
}
void __print(int n){
// भाजक प्रिंट करने का फंक्शन
for(auto x : divisors[n])
cout << x << " ";
cout << "\n";
}
int main() {
findsieve(100000); // हम 10^5 तक छलनी और भाजक को हार्डकोड करते हैं
int n = 6; // दिया गया n
__print(n);
n = 30; // नया n
__print(n);
return 0;
}
आउटपुट
1 2 3 6 1 2 3 5 6 10 15 30
उपरोक्त कोड की व्याख्या
इस दृष्टिकोण में, हम एराटोस्थनीज की छलनी के समान अवधारणा का पालन करते हैं। हम 10^5 तक हर संख्या के भाजक खोजते हैं। जब हमें q क्वेरी दी जाती हैं, तो हमें भाजक खोजने की आवश्यकता नहीं होती, इसलिए जब q क्वेरी पूछी जाती हैं तो हमारी समय जटिलता काफी कम हो जाती है। इसलिए, हमारी जटिलता O(Q*N) हो जाती है, जहां Q हमारे द्वारा निपटाई जाने वाली क्वेरी की संख्या है, और N n के भाजक की संख्या है।
निष्कर्ष
इस लेख में, हम एक समस्या हल करते हैं: n के सभी भाजक प्रिंट करने के लिए क्वेरी जहां हम एराटोस्थनीज की छलनी के सिद्धांत को लागू करते हैं। हमने इस समस्या के लिए C++ प्रोग्राम और इसे हल करने के पूर्ण दृष्टिकोण (सामान्य) को भी सीखा। हम इसी प्रोग्राम को C, Java, Python और अन्य भाषाओं में लिख सकते हैं। आशा है कि आपको यह लेख मददगार लगा होगा।
