นับตัวประกอบเฉพาะร่วมของสองจำนวนใน C++

เราได้รับจำนวนสองจำนวน x และ y งานคือการหาตัวประกอบเฉพาะร่วม (common prime factors) ของทั้งสองจำนวน

ตัวอย่าง

Input − x = 10, y = 20 Output − Common prime factors: 2 5

Input − x = 34, y = 12 Output − Common prime factors: 2

แนวทางการแก้ปัญหา

• หา GCD (ม.ร.ท.) ของ x และ y
• ใช้ Sieve หาจำนวนเฉพาะถึงค่า GCD
• วนลูปจาก 2 ถึง GCD ถ้าเป็นเฉพาะและหาร GCD ลงตัว ให้พิมพ์ค่านั้น

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

#include <bits/stdc++.h>
using namespace std;

#define MAX 100001
bool prime[MAX];

void sieve() {
    fill(prime, prime + MAX, true);
    prime[0] = prime[1] = false;
    for (int p = 2; p * p <= MAX; p++) {
        if (prime[p]) {
            for (int i = p * p; i <= MAX; i += p)
                prime[i] = false;
        }
    }
}

void commonPrime(int x, int y) {
    int g = __gcd(x, y);
    for (int i = 2; i <= g; i++) {
        if (prime[i] && g % i == 0)
            cout << i << " ";
    }
}

int main() {
    sieve();
    int x = 20, y = 30;
    cout << "Common prime factors: ";
    commonPrime(x, y);
    return 0;
}

ผลลัพธ์

Common prime factors: 2 5