Đề bài:

Cho một số nguyên dương N. Hãy tìm một số nguyên tố p ≤ N sao cho p có thể được viết thành tổng của nhiều nhất các số nguyên tố liên tiếp (theo thứ tự từ nhỏ đến lớn bắt đầu từ 2, 3, 5, ...).

Input:

• Một số nguyên dương N (1 ≤ N ≤ 10⁵).

Output:

• Một số nguyên tố p thỏa mãn yêu cầu, có tổng là dãy nguyên tố liên tiếp dài nhất mà vẫn ≤ N.

Ví dụ:

Input: 30

Output: 17

Giải thích:

Dãy dài 1: 2. Tổng là 2. 2 là số nguyên tố và ≤ 30. Ta tạm giữ kết quả là 2 (dãy dài 1).

Dãy dài 2: 2 + 3 = 5. Tổng là 5. 5 là số nguyên tố và ≤ 30. Dãy này dài hơn, nên ta cập nhật kết quả là 5 (dãy dài 2).

Dãy dài 3: 2 + 3 + 5 = 10. Tổng là 10. 10 không phải số nguyên tố. Bỏ qua.

Dãy dài 4: 2 + 3 + 5 + 7 = 17. Tổng là 17. 17 là số nguyên tố và ≤ 30. Dãy này dài hơn, nên ta cập nhật kết quả là 17 (dãy dài 4).

Dãy dài 5: 2 + 3 + 5 + 7 + 11 = 28. Tổng là 28. 28 không phải số nguyên tố. Bỏ qua.

Dãy dài 6: 2 + 3 + 5 + 7 + 11 + 13 = 41. Tổng là 41. Tổng này đã lớn hơn N = 30. Ta không cần xét tiếp nữa vì các tổng sau sẽ còn lớn hơn.