Biểu diễn số dưới dạng tổng số lượng lớn nhất các số nguyên tố bằng C++

Cho N, phân tích thành tổng nhiều số nguyên tố nhất có thể. Sử dụng số nguyên tố nhỏ nhất: 2 và 3. Mọi số đều biểu diễn được bằng tổng 2 và 3.

• N chẵn: N/2 số 2.
• N lẻ: một số 3 + (N-3)/2 số 2.

Ví dụ: N=7 → 2+2+3, N=17 → 2+2+2+2+2+2+2+3.

Ví dụ

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

int main() {
    int N = 7;
    if (N & 1) { cout << "3 +"; N -= 3; }
    while (N != 2) { cout << " 2 +"; N -= 2; }
    cout << " 2";
    return 0;
}

Kết quả

3 + 2 + 2

Kết luận

Phân tích số thành tổng nhiều số nguyên tố nhất bằng cách dùng 2 và 3. Code C++ O(N) (số lượng số hạng).