T-nguyên tố

Hướng tiếp cận

Quan sát then chốt: một số nguyên dương $t$ có đúng ba ước số phân biệt khi và chỉ khi $t=p^2$ với $p$ là số nguyên tố. Khi đó tập ước của $t$ là $\{1,p,p^2\}$.

Chứng minh: nếu $t=p_1^{a_1}{p}_2^{a_2}\cdots p_k^{a_k}$ thì số ước của $t$ là $\prod (a_i+1)$. Để tích này bằng $3$ (số nguyên tố), ta phải có duy nhất một thừa số $a_i+1=3$, tức là $t=p^2$ với $p$ nguyên tố.

Nhận xét quan trọng

1. $x_i\le {10}^{12}$ nên $\sqrt{x_i}\le {10}^6$.
2. Sàng Eratosthenes các số nguyên tố tới ${10}^6$ chỉ tốn $O(N\log \log N)$ thời gian và bộ nhớ $O(N)$.
3. Với mỗi $x$, kiểm tra: lấy $s=\lfloor \sqrt{x}\rfloor$, nếu $s^2=x$ và $s$ là số nguyên tố ($s\ge 2$) thì in YES, ngược lại NO.
4. Khi tính $\sqrt{x}$ trong C++ với sqrtl, nên hiệu chỉnh kết quả bằng cách kiểm tra $s^2$, $(s+1{)}^2$ vì lỗi số thực có thể làm sai lệch ±1. Trong Python dùng math.isqrt cho kết quả chính xác.

Thuật toán

1. Sàng Eratosthenes mảng is_prime[0..10^6].
2. Đọc $n$, sau đó với mỗi $x_i$:
   • Tính $s=\lfloor \sqrt{x_i}\rfloor$ (có hiệu chỉnh).
   • Nếu $s\ge 2$, $s^2=x_i$ và $s$ là số nguyên tố thì in YES, ngược lại in NO.

Độ phức tạp

• Thời gian: $O(M\log \log M+n)$ với $M={10}^6$.
• Bộ nhớ: $O(M)$.