Đếm ước nguyên tố chung của hai số C++

Cho hai số x và y, nhiệm vụ là tìm các ước nguyên tố chung (common prime factors) của chúng.

Ví dụ

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

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

Phương pháp tiếp cận

• Tính GCD (ước chung lớn nhất) của x và y
• Dùng Sieve of Eratosthenes tạo bảng nguyên tố đến MAX
• Duyệt i từ 2 đến GCD: nếu i là nguyên tố và GCD % i == 0 → in i

Ví dụ code C++

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

#define MAX 100001
bool prime[MAX];

void SieveOfEratosthenes() {
    memset(prime, true, sizeof(prime));
    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 common_prime(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() {
    SieveOfEratosthenes();
    int x = 20, y = 30;
    cout << "Common prime factor of two numbers are: ";
    common_prime(x, y);
    return 0;
}

Kết quả

Common prime factor of two numbers are: 2 5