(tongsnt.*)

Cho số nguyên dương \(n\).

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á \(n\). 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,\ldots\)

Dữ liệu vào: Nhập từ bàn phím số nguyên dương \(n\)

Giới hạn:\(\ n \leq 10^{6}\).

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ụ:

Giải thích:

Ví dụ 1: \(n = 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: \(n = 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)\)

Solution:

Ban đầu \(s = 0\)

Xét các số \(x\) từ 2 trở lên, nếu \(x\) là số nguyên tố thì cộng dồn vào \(s\). Kết thúc vòng lặp khi \(s + x > n\)