Câu 3. (4,0 điểm)

Theo quan điểm của người Mazan những số đẹp là số có số lượng các ước của nó là số nguyên tố. Ví dụ: Số 9 có số lượng các ước là 3 gồm các ước (1, 3, 9) vì vậy số 9 là số đẹp. Bạn hãy giúp người Mazan tìm số lượng số đẹp trong đoạn từ 1 đến N cho trước.

Dữ liệu vào: Số nguyên dương N (1 ≤ N ≤ 10⁷).

Kết quả: Một số duy nhất là số lượng số đẹp trong đoạn từ 1 đến N.

Ví dụ:

Ràng buộc:
- Có 40% test tương ứng với 40% số điểm ứng với 1 ≤ N ≤ 10³.
- Có 30% test tương ứng với 30% số điểm ứng với 10³ < N < 5.10⁵.
- Có 30% test tương ứng với 30% số điểm ứng với 10⁶ < N ≤ 10⁷.