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

บทนำ

ในบทช่วยสอนนี้ เราจะหา สองจำนวนเฉพาะที่ต่างกัน (distinct primes) ที่ผลคูณเท่ากับค่าที่กำหนด

ตัวอย่าง

Input: 21
Output: 3 7

ขั้นตอนการแก้ปัญหา

1. สร้างอาร์เรย์ boolean เพื่อจำว่าตัวเลขไหนเป็นจำนวนเฉพาะ (Sieve of Eratosthenes)
2. หาจำนวนเฉพาะทั้งหมดที่น้อยกว่าหรือเท่ากับ n
3. วนลูป i จาก 2 ถึง n-1:
   • ถ้า i เป็นเฉพาะ และ n/i เป็นเฉพาะ และ i ≠ n/i และ i × (n/i) = n
   • พบคำตอบ พิมพ์และหยุด
4. ถ้าไม่พบ พิมพ์ "No pairs"

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

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

void sievePrimes(int n, bool primeStatus[]) {
    primeStatus[0] = primeStatus[1] = false;
    for (int i = 2; i <= n; i++) primeStatus[i] = true;
    
    for (int i = 2; i * i <= n; i++) {
        if (primeStatus[i]) {
            for (int j = i * 2; j <= n; j += i)
                primeStatus[j] = false;
        }
    }
}

int main() {
    int n = 21;
    bool primeStatus[n + 1], pairsFound = false;
    sievePrimes(n, primeStatus);
    
    for (int i = 2; i < n; i++) {
        int pair = n / i;
        if (primeStatus[i] && primeStatus[pair] && pair != i && pair * i == n) {
            cout << i << " " << pair << endl;
            pairsFound = true;
            break;
        }
    }
    if (!pairsFound) cout << "No pairs";
    return 0;
}

ผลลัพธ์

3 7

ข้อสังเกต

• ใช้ Sieve of Eratosthenes หาเฉพาะได้ O(n log log n)
• วนลูปแค่ถึง √n ก็พอ (เพราะ i × pair = n, ถ้า i > √n แล้ว pair < √n จะถูกตรวจไปแล้ว)
• โค้ดต้นฉบับวนถึง n-1 ทำงานช้ากว่าจำเป็น

สรุป

หาคู่จำนวนเฉพาะที่คูณได้ n ใช้ Sieve + วนลูปหาคู่ หากมีคำถาม สามารถถามได้ในส่วนความคิดเห็นครับ