दी गई समस्या में, हमें दिए गए पूर्णांक n के सभी भाजक मुद्रित करने हैं।
Input: 15 Output: 1 3 5 15 Explanation Divisors of 15 are: 1,3, 5, 15 Input: 30 Output: 1 2 3 5 15 30
दी गई समस्या में, हम n के सभी भाजक को खोजने के लिए एराटोस्थनीज की चलनी में प्रयुक्त दृष्टिकोण को लागू कर सकते हैं।
समाधान खोजने के लिए दृष्टिकोण
दिए गए दृष्टिकोण में, हम उस अवधारणा को लागू करेंगे जिसमें एराटोस्थनीज की चलनी आधारित है और n के भाजक ज्ञात करेंगे।
उदाहरण
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
vector<int> divisors[100001]; // our vector containing number with all of its divisors
void findsieve(int max) { // filling data in vector divisors till 10e5
for(int i = 1; i <= max; i++) {
for(int j = i; j <= max; j += i)
divisors[j].push_back(i);
}
}
void __print(int n){ // the function to print divisors
for(auto x : divisors[n])
cout << x << " ";
cout << "\n";
}
int main() {
findsieve(100000); // we hardcode the sieve and divisors till 10e5
int n = 6; // the given n
__print(n);
n = 30; // new n
__print(n);
return 0;
} आउटपुट
1 2 3 6 1 2 3 5 6 10 15 30
उपरोक्त कोड की व्याख्या
इस दृष्टिकोण में, हम इरेटोस्थनीज की छलनी के समान अवधारणा का पालन करते हैं। हम 105 तक प्रत्येक संख्या के भाजक पाते हैं। जब हमें q प्रश्न दिए जाते हैं, तो हमें भाजक खोजने की आवश्यकता नहीं होती है, इसलिए q प्रश्न पूछे जाने पर यह हमारे समय की जटिलता को काफी कम कर देता है। इसलिए, हमारी जटिलता O(Q*N) बन जाती है, जहां Q हमारे द्वारा पूछे जाने वाले प्रश्नों की संख्या है, और N, n के भाजक की संख्या है।
निष्कर्ष
इस लेख में, हम एक समस्या का समाधान करते हैं:n के सभी भाजक को मुद्रित करने के लिए प्रश्न जहां हम एराटोस्थनीज की चलनी के सिद्धांत को लागू करते हैं। हमने इस समस्या के लिए C++ प्रोग्राम और संपूर्ण दृष्टिकोण (Normal) भी सीखा जिसके द्वारा हमने इस समस्या को हल किया। हम उसी प्रोग्राम को अन्य भाषाओं जैसे सी, जावा, पायथन और अन्य भाषाओं में लिख सकते हैं। हमें उम्मीद है कि आपको यह लेख मददगार लगा होगा।
