Một số nguyên dương được gọi là gần nguyên tố (almost prime) nếu nó có đúng hai ước số nguyên tố phân biệt. Ví dụ, , , là các số gần nguyên tố. Các số như (chỉ có một ước nguyên tố là 2), (có ba ước nguyên tố) thì không phải.
Cho một số nguyên , hãy đếm số lượng các số gần nguyên tố trong khoảng từ đến .
Dữ liệu: Một dòng duy nhất chứa số nguyên .
Kết quả: Một số nguyên duy nhất là số lượng các số gần nguyên tố không vượt quá .
Ví dụ:
Dữ liệu:
20
Kết quả:
7
Giải thích: Các số gần nguyên tố từ 1 đến 20 là: . Có tổng cộng 7 số.
