Mô tả và yêu cầu

Cho số nguyên dương 𝑛.
Yêu cầu: Hãy cho biết có nhiều nhất bao nhiêu số nguyên tố khác nhau mà tổng của chúng
không vượt quá 𝑛. Biết rằng số nguyên tố là số nguyên có giá trị lớn hơn 1 và chỉ có 2 ước số
là 1 và chính nó. Các số nguyên tố đầu tiên là: 2, 3, 5, 7,11, 13, 17, 19, 23, …
Dữ liệu vào: Nhập từ bàn phím số nguyên dương 𝑛
Giới hạn: 𝑛 ≤ 106.
Kết quả: ghi ra màn hình một số nguyên duy nhất là số lượng số nguyên tố nhiều nhất thỏa
mãn yêu cầu bài toán.

Ví dụ

Input      Output             Input     Output
                             6          2                  100       9
    Giải thích:
    Ví dụ 1: 𝑛   =  6.
    Có nhi  ều nhất 2 số nguyên t   ố khác nhau có t  ổng không vư    ợt quá 6 (2  +  3  =  5)
    Ví dụ 2: 𝑛   =  100.
Có nhiều nhất 9 số nguyên tố khác nhau là có tổng không vượt quá 100 (2                 +  3 +  5 +  7 +
11 +  13  +  17  +  19  +  23  =  100)