इस समस्या में, हमें दो पूर्णांक मान N और k दिए गए हैं। हमारा कार्य प्राकृतिक संख्या N के k-वें सबसे छोटे भाजक को ज्ञात करना है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट : N = 15, k = 3 आउटपुट : 5
व्याख्या −
15 के गुणनखंड 1, 3, 5, 15 हैं। तीसरा सबसे छोटा 5 है।
समाधान दृष्टिकोण
समस्या का एक सरल समाधान संख्या के गुणनखंडों को ढूंढना और उन्हें सॉर्टेड तरीके से संग्रहीत करना और k-वां मान प्रिंट करना है।
सॉर्टिंग के लिए, हम root(N) तक लूप करेंगे और जांचेंगे कि N, i से विभाज्य है या नहीं। और i और (N/i) के मान को एक सरणी में संग्रहीत करेंगे और इसे सॉर्ट करेंगे। इस सॉर्टेड सरणी से, k-वां मान प्रिंट करें।
उदाहरण
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम
#include <bits/stdc++.h> using namespace std; void findFactorK(int n, int k){ int factors[n/2]; int j = 0; for (int i = 1; i <= sqrt(n); i++) { if (n % i == 0) { factors[j] = i; j++; if (i != sqrt(n)){ factors[j] = n/i; j++; } } } sort(factors, factors + j); if (k > j) cout<<"मौजूद नहीं"; else cout<<factors[k-1]; } int main(){ int N = 16, k = 3; cout<<k<<"-वां सबसे छोटा भाजक संख्या "<<N<<" का है "; findFactorK(N, k); return 0; } आउटपुट
3-वां सबसे छोटा भाजक संख्या 16 का है 4
एक अन्य दृष्टिकोण
समस्या को हल करने का एक अन्य दृष्टिकोण दो सरणियों का उपयोग करना है जो सॉर्टेड हैं।
एक मान i संग्रहीत करता है, आरोही क्रम में सॉर्टेड।
दूसरा मान N/i संग्रहीत करता है, अवरोही क्रम में सॉर्टेड।
हम किसी भी सरणी से k-वां सबसे छोटा मान ढूंढेंगे। यदि k सरणी के आकार से बड़ा है, तो यह दूसरी सरणी में अंत से मौजूद है।
अन्यथा यह पहली सरणी में मौजूद है।
उदाहरण
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम
#include <bits/stdc++.h> using namespace std; void findFactorK(int n, int k){ int factors1[n/2]; int factors2[n/2]; int f1 = 0,f2 = 0; for (int i = 1; i <= sqrt(n); i++) { if (n % i == 0) { factors1[f1] = i; f1++; if (i != sqrt(n)){ factors2[f2] = n/i; f2++; } } } if (k > (f1 + f2)) cout<<"मौजूद नहीं"; else{ if(k <= f1) cout<<factors1[f1-1]; else cout<<factors2[k - f2 - 1]; } } int main(){ int N = 16, k = 3; cout<<k<<"-वां सबसे छोटा भाजक संख्या "<<N<<" का है "; findFactorK(N, k); return 0; } आउटपुट
3-वां सबसे छोटा भाजक संख्या 16 का है 4
