এই সমস্যায়, আমাদের একটি সংখ্যা দেওয়া হয়েছে, এবং আমাদের সমস্ত অনন্য মৌলিক গুণনীয়ক এবং তাদের শক্তিগুলি খুঁজে বের করতে হবে যা সংখ্যাটিকে ভাগ করে।
বিষয়টি বোঝার জন্য একটি উদাহরণ নেওয়া যাক −
Input: 55 Output: 5 power 1 11 power 1
ব্যাখ্যা -
55 5 এবং 11 দ্বারা বিভাজ্য।
এই সমস্যাটি সমাধান করার জন্য, সমস্যা সমাধানের একটি সহজ পদ্ধতি হল N-এর মৌলিক গুণনীয়কগুলি খুঁজে বের করা। তারপর N সংখ্যাটিকে ভাগ করে এমন মৌলিক সংখ্যার শক্তি খুঁজে বের করুন এবং এটি মুদ্রণ করুন।
অ্যালগরিদম
দক্ষ পদ্ধতি
Step 1: Find an array s[N+1]. s[i] = prime factor of i dividing N. Step 2: Find all powers of i. prime = s[N] and pow = 1. Step 3: While (N > 1) : Step 3.1: N /= s[N]; Step 3.2: if(prime = s[N]) : pow++ Step 4: print prime and pow.
উদাহরণ
#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
