Số gần nguyên tố

Đề 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ụ

10

13

100

87

20

13

1

0

50

87

Giải thích

Test 1

Các số gần nguyên tố \( \leq 10 \): \( \{4, 9\} \). Tổng: \( 4 + 9 = 13 \).

Test 2

Các số gần nguyên tố \( \leq 100 \): \( \{4, 9, 25, 49\} \). Tổng: \( 4 + 9 + 25 + 49 = 87 \).

Test 3

Các số gần nguyên tố \( \leq 20 \): \( \{4, 9\} \). Tổng: \( 4 + 9 = 13 \).

Test 4

Không có số gần nguyên tố nào \( \leq 1 \).

Test 5

Các số gần nguyên tố \( \leq 50 \): \( \{4, 9, 25, 49\} \). Tổng: \( 4 + 9 + 25 + 49 = 87 \).

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} \).