Đề bài

Một số được gọi là số gần nguyên tố nếu nó có đúng 3 ước số khác nhau. Ví dụ:

• \( 4 \) là số gần nguyên tố vì các ước số của nó là \( \{1, 2, 4\} \).
• \( 9 \) là số gần nguyên tố vì các ước số của nó là \( \{1, 3, 9\} \).
• \( 6 \) không phải là số gần nguyên tố vì nó có \( 4 \) ước số \( \{1, 2, 3, 6\} \).

Cho một số nguyên dương \( n \), hãy tính tổng tất cả các số gần nguyên tố nhỏ hơn hoặc bằng \( n \).

Dữ liệu vào

• Một số nguyên \( n \) \((1 \leq n \leq 10^{12})\).

Kết quả ra

• Một số nguyên duy nhất: tổng tất cả các số gần nguyên tố \( \leq n \).

Ví dụ

Ràng buộc

1. \( 1 \leq n \leq 10^6 \): Subtask 1 (30 điểm).
2. \( 1 \leq n \leq 10^{12} \): Subtask 2 (70 điểm).

Gợi ý

• Một số gần nguyên tố luôn có dạng \( p^2 \), với \( p \) là số nguyên tố.
• Cần áp dụng thuật toán hiệu quả cho \( n \leq 10^{12} \).