প্রদত্ত সমস্যায়, আমাদের একটি প্রদত্ত পূর্ণসংখ্যা 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++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি (সাধারণ) শিখেছি যার মাধ্যমে আমরা এই সমস্যার সমাধান করেছি। আমরা অন্যান্য ভাষা যেমন সি, জাভা, পাইথন এবং অন্যান্য ভাষায় একই প্রোগ্রাম লিখতে পারি। আমরা আশা করি আপনার এই নিবন্ধটি সহায়ক হবে৷
