ধরুন দুটি সংখ্যা আছে। একটি সংখ্যা মৌলিক গুণনীয়ক বা দ্বিতীয় সংখ্যা দ্বারা বিভাজ্য কিনা তা আমাদের পরীক্ষা করতে হবে। ধরুন একটি সংখ্যা হল 120৷ মৌলিক গুণনীয়কগুলি হল {2, 3, 5}, আরেকটি সংখ্যা হল 75, এখানে মৌলিক গুণনীয়কগুলি হল {3, 5}৷ যেহেতু 120 3 এবং 5 দ্বারা বিভাজ্য, তাই সিদ্ধান্ত হল হ্যাঁ৷
যদি একটি সংখ্যা 1 হয়, তাহলে এর কোন মৌলিক ভাজক নেই, তাই উত্তরটি সত্য। অন্যথায় আমাদের এই দুটি সংখ্যার GCD খুঁজে বের করতে হবে। যদি GCD 1 হয়, তাহলে তারা সহ-প্রধান। তাই উত্তর মিথ্যা। যদি GCD> 1 হয়, তাহলে GCD-এ মৌলিক ভাজক থাকে, যা xকেও ভাগ করে (x প্রথম সংখ্যা হিসেবে)। যদি আমাদের সকলের অনন্য মৌলিক ভাজক থাকে তাহলে দ্বিতীয় সংখ্যা 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;
} এর সমস্ত মৌলিক গুণনীয়ক দ্বারা বিভাজ্য হতে পারে না আউটপুট
120 can be divisible by all prime factors of 75
