Số lượng số nguyên tố tối đa có tổng bằng N trong C++

Cho số N. Tìm số lượng số nguyên tố lớn nhất mà tổng của chúng bằng N.

Phân tích

Để tối đa hóa số lượng số nguyên tố, ta nên dùng các số nguyên tố nhỏ nhất: 2 và 3.

• N chẵn: Dùng toàn số 2 → số lượng = N/2.
• N lẻ: Dùng một số 3 và các số 2 còn lại → số lượng = (N-3)/2 + 1 = (N-1)/2 = N/2 (lấy nguyên).

Cả 2 trường hợp đều cho kết quả N/2 (chia nguyên).

Ví dụ

N = 9 (lẻ): 9/2 = 4. Phân tích: 2+2+2+3 = 9 (4 số nguyên tố).

Ví dụ minh họa

#include <iostream>
using namespace std;

int maxPrimeCount(int n) {
    // Với N lẻ: (N-1)/2 = N/2 (chia nguyên)
    // Với N chẵn: N/2
    return n / 2;
}

int main() {
    int n = 9;
    cout << "The maximum number of primes whose sum is equal to " << n 
         << " is " << maxPrimeCount(n);
    return 0;
}

Kết quả

The maximum number of primes whose sum is equal to 9 is 4

Lưu ý: Điều này đúng vì theo ước lượng Goldbach, mọi số chẵn ≥ 4 đều là tổng của 2 số nguyên tố, và số lẻ ≥ 5 là tổng của 3 số nguyên tố. Với N nhỏ (1,2,3) cần xử lý riêng nhưng công thức N/2 vẫn cho kết quả đúng (1/2=0, 2/2=1, 3/2=1).