এই সমস্যায়, আমাদের একটি পূর্ণসংখ্যা দেওয়া হয়েছে N <=10^18। আমাদের কাজ হল সংখ্যার সমস্ত প্রাইম ফ্যাক্টর প্রিন্ট করা এবং সাথে সেখানে উপস্থিতির ফ্রিকোয়েন্সি।
সমস্যাটি বোঝার জন্য একটি উদাহরণ দেওয়া যাক,
Input: 100 Output: 2 2 5 2 Explanation: prime factorization of 100 = 2 * 2 * 5 * 5.
এই সমস্যাটি সমাধান করার জন্য, আমাদের সংখ্যাটির মৌলিক গুণনীয়কগুলি খুঁজে বের করতে হবে এবং তারপরে তাদের ফ্রিকোয়েন্সি গণনা করতে হবে৷
এর জন্য, আমরা ফ্যাক্টর হিসাবে 2 এর ফ্রিকোয়েন্সি পরীক্ষা করব এবং সংখ্যাটিকে 2 দ্বারা ভাগ করব। তারপর 3 থেকে বর্গমূল n পর্যন্ত পরীক্ষা করব। প্রতিটি মৌলিক সংখ্যার ফ্রিকোয়েন্সি ভাগ করুন এবং বৃদ্ধি করুন যা সংখ্যাটির একটি গুণনীয়ক। এবং সংখ্যাটি 1 হয়ে গেলে থামুন। তারপর সেখানে ফ্রিকোয়েন্সি সহ সমস্ত প্রাইম প্রিন্ট করুন।
নীচের কোডটি আমাদের সমাধানের বাস্তবায়ন দেখায়,
উদাহরণ
#include <iostream>
#include <math.h>
using namespace std;
void factorize(long long n){
int count = 0;
while (!(n % 2)) {
n/= 2;
count++;
}
if (count)
cout<<2<<"\t"<<count<<endl;
for (long long i = 3; i <= sqrt(n); i += 2) {
count = 0;
while (n % i == 0) {
count++;
n = n / i;
}
if (count)
cout<<i<<"\t"<<count<<endl;
}
if (n > 2)
cout<<n<<"\t"<<1<<endl;
}
int main() {
long long N = 21000;
cout<<"The prime factors and their frequencies of the number "<<N<<" are \n";
factorize(N);
return 0;
} আউটপুট
The prime factors and their frequencies of the number 21000 are 2 3 3 1 5 3 7 1
