Đầu tiên, chúng ta cần tìm các số nguyên tố nhỏ hơn hoặc bằng ~1000~ và lưu chúng vào mảng ~a~.

Bây giờ,ta có một tập hợp các số nguyên tố nhỏ hơn hoặc bằng ~1000~ và cần tìm ra cách để tạo ra tổng bằng ~N~ bằng cách sử dụng các số nguyên tố này, mỗi số nguyên tố có thể sử dụng tối đa hai lần. Mục tiêu là tìm số lượng các số nguyên tố lớn nhất có thể để tổng của chúng bằng ~N~.

Chúng ta sẽ sử dụng quy hoạch động ở đây:

Gọi ~dp[x]~ là số lượng nhiều nhất các số được chọn từ dãy ~a~ để tổng của chúng bằng ~x~. $$ dp[x]= \begin{cases} 0 &\text{nếu } x=0 \\ -\infty &\text{nếu } x \in [1,1000] \end{cases} $$

Điều này có nghĩa là:

~dp[0] = 0:~ Không có số nào tạo ra tổng bằng ~0~.

~dp[x] = -\infty~ với mọi ~s~ từ ~1~ đến ~1000~: Ban đầu, chúng ta chưa tìm ra cách nào để tạo ra các tổng này.

Xét từng số nguyên tố ~a[i]~ trong mảng ~a~

Xét ~a[i]~ được sử dụng ~1~ lần:

Chúng ta cần xác định liệu việc thêm số nguyên tố ~a[i]~ vào một tổng nhỏ hơn (tức là ~x - a[i]~) có thể tạo ra một tổng ~x~ với số lượng các số nguyên tố được chọn tối đa hay không.Tức là:

Nếu không thêm ~a[i]~, giá trị của ~dp[x]~ vẫn giữ nguyên.

Nếu thêm ~a[i]~, giá trị của ~dp[x]~ sẽ được cập nhật thành ~dp[x - a[i]] + 1~(là số lượng lớn nhất các số nguyên tố để tạo ra tổng ~s - a[i]~. Khi thêm số nguyên tố ~a[i]~ vào tổng này, tổng sẽ là ~s~, và số lượng các số nguyên tố được chọn sẽ tăng thêm ~1~) nếu giá trị này lớn hơn giá trị hiện tại của ~dp[x]~.

Cách làm xét ~a[i]~ được sử dụng ~2~ lần cũng tương tự

Từ đó ta suy ra được công thức

$$ dp[x]= \begin{cases} \max(dp[s], dp[s - a[i]] + 1) & \text{nếu sử dụng } a[i] \text{ một lần} \\ \max(dp[s], dp[s - 2 * a[i]] + 2) & \text{nếu sử dụng } a[i] \text{ hai lần} \end{cases} $$

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

const int MAXN = 1000;
const int INF = -1e9;
vector<int> p;

void sieve() {
    vector<bool> ok(1005, true);
    ok[0] = ok[1] = false;
    for (int i = 2; i <= 1000; ++i) {
        if (ok[i]) {
            p.push_back(i);
            for (int j = i * i; j <= 1000; j += i) {
                ok[j] = false;
            }
        }
    }
}

void sol(int n){
    vector<int> dp(n + 1, -1e9);
    dp[0] = 0;
    for(int x : p){
        for(int s = n; s >= x; --s){
            if(s >= x) dp[s] = max(dp[s], dp[s - x] + 1);
            if(s >= 2 * x) dp[s] = max(dp[s], dp[s - 2 * x] + 2);
        }
    }
    dp[1]=1;
    cout << dp[n] << "\n";
}

int main() {
    int n;
    sieve();
    while(cin >> n) sol(n);
    return 0;
}