ตรวจสอบตัวเลขหารด้วยตัวหารเฉพาะของอีกตัวได้หมดใน C++

ปัญหา

ให้ตัวเลข a และ b ตรวจสอบว่า a หารด้วยตัวหารเฉพาะ (prime factors) ของ b ลงตัวหมดหรือไม่

ตัวอย่าง: a=120, b=75

• Prime factors ของ 120: 2, 3, 5
• Prime factors ของ 75: 3, 5
• 120 หาร 3 และ 5 ลงตัว → Yes

ข้อสังเกตสำคัญ

a หารตัวหารเฉพาะของ b ลงตัวหมด ⟺ ทุกตัวหารเฉพาะของ b ก็เป็นตัวหารของ a

⟺ gcd(a, b) มีตัวหารเฉพาะครอบคลุมตัวหารเฉพาะของ b

⟺ b / gcd(a, b) ไม่มีตัวหารเฉพาะใหม่ (นอกเหนือจากที่อยู่ใน a)

อัลกอริทึมแบบ Recursive (มีประสิทธิภาพ)

1. ถ้า b == 1 → true (1 ไม่มีตัวหารเฉพาะ)
2. คำนวณ g = gcd(a, b)
3. ถ้า g == 1 → false (a, b คอไพร้ม แต่ b > 1)
4. เรียกซ้ำกับ (a, b/g) → ตัดตัวหารที่ซ้ำกันออก

ตัวอย่างโค้ด C++

#include <iostream>
#include <algorithm> // __gcd หรือ std::gcd (C++17)
using namespace std;

bool isDivisibleByAllPrimeFactors(int a, int b) {
    if (b == 1) return true;           // Base case
    int g = __gcd(a, b);               // C++17: std::gcd(a, b)
    if (g == 1) return false;          // ไม่มีตัวหารร่วม
    return isDivisibleByAllPrimeFactors(a, b / g); // ตัด g ออก แล้วเช็คต่อ
}

int main() {
    int a = 120, b = 75;
    if (isDivisibleByAllPrimeFactors(a, b))
        cout << a << " is divisible by all prime factors of " << b;
    else
        cout << a << " is NOT divisible by all prime factors of " << b;
    return 0;
}

ผลลัพธ์

120 is divisible by all prime factors of 75

การทำงานทีละขั้น (a=120, b=75)

1. b=75, gcd(120,75)=15 → เรียก (120, 75/15=5)
2. b=5, gcd(120,5)=5 → เรียก (120, 5/5=1)
3. b=1 → return true

ตัวอย่างเพิ่มเติม

ความซับซ้อน

• เวลา: O(log min(a,b)) ต่อ recursive call, รวม O(log² max(a,b))
• พื้นที่: O(log max(a,b)) สำหรับ recursion stack