দেওয়া সমস্যায়, আমাদের একটি পূর্ণসংখ্যা n-এর সব ভাজক প্রিন্ট করতে হবে।
Input: 15 Output: 1 3 5 15 Explanation 15-এর ভাজকها: 1,3, 5, 15 Input: 30 Output: 1 2 3 5 15 30
দেওয়া সমস্যায়, আমরা n-এর সব ভাজক খুঁজে বের করার জন্য এরাটোस्थেনিসের সিভ (sieve of Eratosthenes) এর কনসেপ্ট ব্যবহার করতে পারি।
সমাধানের পদ্ধতি
দেওয়া পদ্ধতিতে, আমরা এরাটোস্থেনিসের সিভের ভিত্তিতে কনসেপ্ট প্রয়োগ করে n-এর ভাজক খুঁজে বের করব।
উদাহরণ
#include <bits/stdc++.h> #define MOD 1000000007 using namespace std; vector<int> divisors[100001]; // প্রতিটি সংখ্যার ভাজক ধারণকারী ভেক্টর void findsieve(int max) { // ১০^৫ পর্যন্ত ভেক্টরে ডেটা ফিল করুন 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); // ১০^৫ পর্যন্ত সিভ ও ভাজক হার্ডকোড 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
উপরোক্ত কোডের ব্যাখ্যা
এই পদ্ধতিতে, আমরা এরাটোস্থেনিসের সিভের মতো কনসেপ্ট অনুসরণ করি। আমরা ১০^৫ পর্যন্ত প্রতিটি সংখ্যার ভাজক খুঁজে বের করি। যখন আমাদের q সংখ্যক কোয়েরি দেওয়া হবে, তবে আমাদের বারবার ভাজক খুঁজে বের করতে হবে না, তাই টাইম কমপ্লেক্সিটি драষ্টিকভাবে কমে যায়। আমাদের কমপ্লেক্সিটি হয় O(Q*N), যেখানে Q হল কোয়েরির সংখ্যা এবং N হল n-এর ভাজক সংখ্যা।
উপসংহার
এই আর্টিকেলে, আমরা একটি সমস্যা সমাধান করেছি: n-এর সব ভাজক প্রিন্ট করার কোয়েরি, যেখানে এরাটোস্থেনিসের সিভের নীতি প্রয়োগ করা হয়েছে। আমরা এই সমস্যার জন্য C++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি (সাধারণ) শিখেছি। একই প্রোগ্রামটি C, Java, Python এবং অন্যান্য ভাষায়ও লিখা যায়। আশা করি আপনি এই আর্টিকেলটিকে উপকারী পাবেন।
