এই সমস্যায়, আমাদের N এবং k দুটি পূর্ণসংখ্যার মান দেওয়া হয়েছে। আমাদের কাজ হল একটি প্রাকৃতিক সংখ্যা N এর k-তম ক্ষুদ্রতম ভাজক খুঁজে বের করা .
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
Input : N = 15, k = 3 Output : 5
ব্যাখ্যা −
Factors of 15 are 1, 3, 5, 15 3rd smallest is 5
সমাধান পদ্ধতি
সমস্যার একটি সহজ সমাধান হল সংখ্যার ফ্যাক্টর খুঁজে বের করা এবং সেগুলিকে সাজানো পদ্ধতিতে সংরক্ষণ করা এবং kth মান মুদ্রণ করা।
সাজানোর জন্য, আমরা root(N) পর্যন্ত লুপ করব এবং N দ্বারা i দ্বারা বিভাজ্য কিনা তা পরীক্ষা করব। এবং একটি অ্যারেতে i এবং (N/i) এর মান সংরক্ষণ করুন এবং এটি সাজান। এই সাজানো অ্যারে থেকে, k-th মান প্রিন্ট করুন।
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম
#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<<"Doesn't Exist";
else
cout<<factors[k-1];
}
int main(){
int N = 16,
k = 3;
cout<<k<<"-th smallest divisor of the number "<<N<<" is ";
findFactorK(N, k);
return 0;
} আউটপুট
3-th smallest divisor of the number 16 is 4
অন্য পদ্ধতি
সমস্যা সমাধানের আরেকটি পদ্ধতি হল দুটি অ্যারে ব্যবহার করা যা সাজানো হয়েছে।
এক সঞ্চয় মান i, ক্রমবর্ধমান ক্রমে সাজানো।
অন্যান্য সঞ্চয় মান N/i, নিচের ক্রমে সাজানো।
আমরা দুটি অ্যারের মধ্যে kth সবচেয়ে ছোট মানের ফর্মটি খুঁজে পাব। যদি 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<<"Doesn't Exist";
else{
if(k <= f1)
cout<<factors1[f1-1];
else
cout<<factors2[k - f2 - 1];
}
}
int main(){
int N = 16,
k = 3;
cout<<k<<"-th smallest divisor of the number "<<N<<" is ";
findFactorK(N, k);
return 0;
} আউটপুট
3-th smallest divisor of the number 16 is 4
