মনে করুন দুটি সংখ্যা আছে। আমাদের চেক করতে হবে একটি সংখ্যা অন্য সংখ্যার সব প্রাইম ফ্যাক্টর দিয়ে বিভাজ্য কিনা। উদাহরণস্বরূপ, একটি সংখ্যা ১২০। এর প্রাইম ফ্যাক্টর {২, ৩, ৫}। অন্য সংখ্যা ৭৫, এর প্রাইম ফ্যাক্টর {৩, ৫}। ১২০ যেহেতু ৩ এবং ৫ দিয়ে বিভাজ্য, তাই সিদ্ধান্ত হচ্ছে হ্যাঁ।
যদি একটি সংখ্যা ১ হয়, তবে তার কোনো প্রাইম ডিভাইজার নেই, তাই উত্তর True। অন্যথায় দুটি সংখ্যার GCD বের করতে হবে। যদি GCD ১ হয়, তবে তারা কো-প্রাইম, তাই উত্তর false। যদি GCD > ১ হয়, তবে GCD-তে প্রাইম ডিভাইজার থাকে যা x কেও ভাগ করে (x হল প্রথম সংখ্যা)। যদি সব ইউনিক প্রাইম ডিভাইজার থাকে iff দ্বিতীয় সংখ্যা y / GCD-তে এমন ইউনিক প্রাইম ডিভাইজার থাকে। রিকার্শন ব্যবহার করে (x, y/GCD) জোড়ার জন্য ইউনিকনেস চেক করতে হবে।
উদাহরণ কোড
#include <iostream>
#include <algorithm>
using namespace std;
bool isDivisible(int a, int b) {
if (b == 1)
return true;
int gcd = __gcd(a, b);
if (gcd == 1)
return false;
return isDivisible(a, b / gcd);
}
int main() {
int a = 120, b = 75;
if (isDivisible(a, b))
cout << a << " can be divisible by all prime factors of " << b;
else
cout << a << " can NOT be divisible by all prime factors of " << b;
return 0;
}
আউটপুট
120 can be divisible by all prime factors of 75
