Tìm 2 số nguyên tố khác nhau có tích bằng N trong C++

Cho N, tìm 2 số nguyên tố phân biệt p, q sao cho p*q = N.

Ví dụ

N=24 → Không có (24 = 2*12, 3*8, 4*6 - không có cặp nguyên tố).

N=15 → 3 và 5.

Thuật toán

• Sàng Eratosthenes tìm số nguyên tố ≤ N.
• Duyệt i từ 2 đến √N, nếu i nguyên tố và N%i==0 và N/i nguyên tố và i != N/i → tìm thấy.

Code C++

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

void sieve(int n, vector<bool>& isPrime) {
    isPrime.assign(n+1, true);
    isPrime[0] = isPrime[1] = false;
    for (int p = 2; p*p <= n; p++)
        if (isPrime[p])
            for (int i = p*p; i <= n; i += p) isPrime[i] = false;
}

void primePairProduct(int n) {
    vector<bool> isPrime;
    sieve(n, isPrime);
    
    for (int i = 2; i*i <= n; i++) {
        if (isPrime[i] && n % i == 0) {
            int j = n / i;
            if (j != i && isPrime[j]) {
                cout << i << " " << j;
                return;
            }
        }
    }
    cout << "No prime pair exist";
}

int main() {
    primePairProduct(24); // No prime pair exist
    return 0;
}

Kết quả

No prime pair exist

Độ phức tạp: O(N log log N) cho sàng, O(√N) kiểm tra.