এই সমস্যায়, আমাদের একটি পূর্ণসংখ্যা N ≤ 10¹⁸ দেওয়া আছে। আমাদের কাজ হলো সংখ্যার সকল প্রাইম ফ্যাক্টর ও তাদের বায়ার্দি (frequency) প্রিন্ট করা।
উদাহরণ:
ইনপুট: 100 আউটপুট: 2 2 5 2 ব্যাখ্যা: 100-এর প্রাইম ফ্যাক্টরাইজেশন = 2 * 2 * 5 * 5।
সমাধানের জন্য, আমরা সংখ্যার প্রাইম ফ্যাক্টর বের করে তাদের ফ্রিকোয়েন্সি গণনা করব। প্রথমে ২ কতবার ফ্যাক্টর তা চেক করব এবং সংখ্যাকে ২ দিয়ে ভাগ করব। তারপর ৩ থেকে √n পর্যন্ত চেক করব। প্রতিটি প্রাইম ফ্যাক্টরের জন্য ভাগ করে ফ্রিকোয়েন্সি বাড়াব। সংখ্যা ১ হলে থামব। সব প্রাইম ও তাদের ফ্রিকোয়েন্সি প্রিন্ট করব।
উদাহরণ
#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
