หา 2 จำนวนเฉพาะที่ต่างกัน ที่ผลคูณเท่ากับ N ใน C++

โจทย์: กำหนด N หา 2 จำนวนเฉพาะ p, q (p ≠ q) ที่ p × q = N

อัลกอริธึม: Sieve + Check Pairs

1. Sieve of Eratosthenes หา primes ≤ N
2. วน i = 2..N:
• ถ้า i prime และ N%i==0 และ N/i prime และ N/i ≠ i → พบคู่

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

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

void findingPrimeNumbers(int n, bool isPrime[]) {
    fill(isPrime, isPrime + n + 1, true);
    isPrime[0] = isPrime[1] = false;
    for (int p = 2; p * p <= n; p++)
        if (isPrime[p])
            for (int i = p * 2; i <= n; i += p)
                isPrime[i] = false;
}

void calcPairPrime(int n) {
    bool isPrime[n + 1];
    findingPrimeNumbers(n, isPrime);
    for (int i = 2; i < n; i++) {
        int x = n / i;
        if (isPrime[i] && isPrime[x] && x != i && x * i == n) {
            cout << i << " " << x;
            return;
        }
    }
    cout << "No prime pair exist";
}

int main() {
    calcPairPrime(24); // No prime pair exist
}

อินพุต

24

เอาต์พุท

No prime pair exist

ตัวอย่างที่มีคำตอบ

N = 15 → 3 5 (3×5=15, ทั้งคู่เป็น prime)

Complexity

• Time: O(N log log N) sieve + O(N) check
• Space: O(N)