এই সমস্যায়, একটি সংখ্যা N দেওয়া থাকে এবং আমাদের সেই সংখ্যাকে ভাগ করার সব অনন্য প্রাইম ফ্যাক্টর এবং তাদের ক্ষমতা (পাওয়ার) খুঁজে বের করতে হবে।
উদাহরণ দিয়ে বুঝি:
ইনপুট: 55 আউটপুট: 5 power 1 11 power 1
ব্যাখ্যা: 55, 5 এবং 11 দ্বারা বিভাজ্য।
এই সমস্যাটি সমাধান করার একটি সহজ পদ্ধতি হলো N-এর প্রাইম ফ্যাক্টরগুলো খুঁজে বের করা। তারপর সেই প্রাইম নম্বরটির ক্ষমতা বের করা যাতে সেটি N কে ভাগ করে। তারপর সেটি প্রিন্ট করা।
অ্যালগরিদম
দক্ষ পদ্ধতি
ধাপ ১: একটি অ্যারে s[N+1] খুঁজে বের করুন। s[i] = N কে ভাগ করার i-এর প্রাইম ফ্যাক্টর। ধাপ ২: i-এর সব ক্ষমতা খুঁজে বের করুন। prime = s[N] এবং pow = 1। ধাপ ৩: যতক্ষণ (N > 1): ধাপ ৩.১: N /= s[N]; ধাপ ৩.২: যদি (prime = s[N]) হয়: pow++ ধাপ ৪: prime এবং pow প্রিন্ট করুন।
C++ উদাহরণ
#include<bits/stdc++.h> using namespace std; void primes(int N, int s[]){ vector <bool> prime(N+1, false); for (int i=2; i<=N; i+=2) s[i] = 2; for (int i=3; i<=N; i+=2){ if (prime[i] == false){ s[i] = i; for (int j=i; j*i<=N; j+=2){ if (prime[i*j] == false){ prime[i*j] = true; s[i*j] = i; } } } } } void generatePrimeFactors(int N) { int s[N+1]; primes(N, s); cout<<"Factor\tPower"<<endl; int prime = s[N]; int power = 1; while (N > 1){ N /= s[N]; if (prime == s[N]){ power++; continue; } cout<<prime<<"\t"<<power<<endl; prime = s[N]; power = 1; } } int main() { int N = 55; cout<<"The prime factors are and their powers are :\n"; generatePrimeFactors(N); return 0; }আউটপুট
প্রাইম ফ্যাক্টরগুলো এবং তাদের ক্ষমতা হলো:
Factor Power 5 1 11 1
