สมมุติว่ามีตัวเลขสองตัว เราต้องตรวจสอบว่าจำนวนนั้นหารด้วยตัวประกอบเฉพาะทั้งหมดหรือจำนวนที่สองหารลงตัวหรือไม่ สมมติว่าตัวเลขคือ 120 ตัวประกอบเฉพาะคือ {2, 3, 5} อีกจำนวนหนึ่งคือ 75 ตัวประกอบเฉพาะคือ {3, 5} เนื่องจาก 120 หารด้วย 3 กับ 5 ลงตัว ดังนั้นการตัดสินใจจึงใช่
หากจำนวนหนึ่งเป็น 1 แสดงว่าไม่มีตัวหารเฉพาะ ดังนั้นคำตอบจึงเป็นจริง มิฉะนั้นเราจะต้องหา GCD ของตัวเลขสองตัวนี้ ถ้า GCD เป็น 1 แสดงว่าเป็น co-prime ดังนั้นคำตอบจึงเป็นเท็จ ถ้า GCD คือ> 1 ดังนั้น 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;
} ผลลัพธ์
120 can be divisible by all prime factors of 75
