Biểu diễn số lẻ dưới dạng tổng các số nguyên tố trong C++

Cho số lẻ N. Nhiệm vụ: biểu diễn N dưới dạng tổng các số nguyên tố (tối đa 3 số).

Ví dụ:

Đầu vào: N = 55

Đầu ra: 53 + 2

Phương pháp giải

Dựa trên 3 trường hợp:

• Trường hợp 1: N là số nguyên tố => biểu diễn = N.
• Trường hợp 2: N-2 là số nguyên tố => N = (N-2) + 2.
• Trường hợp 3: N-3 là số chẵn. Theo suy đoán Goldbach, N-3 = p1 + p2 (p1, p2 nguyên tố). => N = 3 + p1 + p2.

Chương trình minh họa

Ví dụ

#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;
}

Kết quả

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