แสดงจำนวนคี่เป็นผลรวมของจำนวนเฉพาะใน C++

ในปัญหานี้ กำหนดให้มีจำนวนคี่ N ภารกิจคือ แสดงจำนวนคี่เป็นผลรวมของจำนวนเฉพาะ

จำนวนเฉพาะที่ใช้ได้สูงสุด 3 จำนวน

ตัวอย่าง

Input: N = 55
Output: 53 + 2

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

จำนวนคี่สามารถแสดงเป็นผลรวมของจำนวนเฉพาะได้ 3 กรณี:

• กรณี 1: ถ้า n เป็นจำนวนเฉพาะ → แสดงเป็น n เพียงตัวเดียว
• กรณี 2: ถ้า (n - 2) เป็นจำนวนเฉพาะ → แสดงเป็น (n-2) + 2
• กรณี 3: (n - 3) เป็นจำนวนคู่ → ใช้ความคิดเห็นของ Goldbach's Conjecture หาจำนวนเฉพาะ A และ (n-3)-A ที่ทั้งคู่เป็นจำนวนเฉพาะ → แสดงเป็น 3 + A + ((n-3)-A)

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

#include <iostream>
using namespace std;

bool isPrime(int x) {
    if (x == 0 || x == 1)
        return false;
    for (int i = 2; i * i <= x; ++i)
        if (x % i == 0)
            return false;
    return true;
}

void primeAsSumofPrime(int n) {
    if (isPrime(n))
        cout << n;
    else if (isPrime(n - 2))
        cout << "2 + " << (n - 2);
    else {
        cout << "3 + ";
        n -= 3;
        for (int i = 0; i < n; i++) {
            if (isPrime(i) && isPrime(n - i)) {
                cout << i << " + " << (n - i);
                break;
            }
        }
    }
}

int main() {
    int n = 561;
    cout << "The number " << n << " expressed as sum of primes is ";
    primeAsSumofPrime(n);
    return 0;
}

ผลลัพธ์

The number 561 expressed as sum of primes is 3 + 11 + 547

หมายเหตุ: Goldbach's Conjecture ระบุว่าจำนวนคู่ทุกตัวที่มากกว่า 2 สามารถแสดงเป็นผลรวมของจำนวนเฉพาะ 2 ตัวได้ (ยังไม่ได้พิสูจน์ทางคณิตศาสตร์แต่ถูกต้องสำหรับตัวเลขขนาดใหญ่มาก)