Solution COUNTPRIME :

• Ý tưởng : sử dụng quy hoạch động để tính trước kết quả với n từ 1 đến 10 000 và rồi với mỗi test thì in ra trong O(1).
• Gọi dp[n][k][0] là số lượng tối đa các số nguyên tố có tổng đúng bằng n và chỉ sử dụng k số nguyên tố đầu tiên mà mỗi số chỉ xuất hiện đúng một lần.
• Gọi dp[n][k][1] là số lượng tối đa các số nguyên tố có tổng đúng bằng n và chỉ sử dụng k số nguyên tố đầu tiên mà số lượng số được xuất hiện hai lần <= 1.
• Việc đầu tiên chúng ta cần làm là tạo một mảng prime là mảng chứa tất cả các số nguyên tố <= 10 000 vì n tối đa chỉ có thể bằng 10 000, việc này có thể thực hiện bằng cách chạy từ 1 đến 10 000 và kiểm tra số đó có phải là số nguyên tố hay không với độ phức tạp là O(10 000 * sqrt(10 000)).
• Gọi m là số lượng các số nguyên tố nằm trong mảng prime.
• Ban đầu là chúng ta cần gán mọi dp[i][j][0] và dp[i][j][1] = -1 tượng trưng cho việc chưa thể tìm được các số nguyên tố trong j số nguyên tố đầu tiên có tổng bằng i.
• Bài toán cơ sở :
• dp[0][i] = 0 với mọi i từ 1 đến m.
• dp[2][i] = 1 với mọi i từ 1 đến m.

• Vì bài này yêu cầu nhập dữ liệu cho đến hết file nên cho những bạn nào chưa biết thì cách để nhập cho đến hết file là : int n; while(cin >> n) { // in ra theo đề bài }
• Sau khi chúng ta hoàn thành được mảng dp rồi thì việc còn lại chỉ đơn giản là in ra kết quả max của dp[n][m][0] và dp[n][m][1].
• Độ phức tạp O(10 000 * sqrt(10 000) + 10 000 * m * 2).