Ba Ước Dương · canuc80k0806 · Thuật toán Canuc80k

Cho một dãy gồm $n$ số nguyên dương. Với mỗi số $x$ , hãy xác định $x$ có đúng ba ước dương phân biệt hay không.

Với từng phần tử, in YES nếu số đó có đúng ba ước; ngược lại in NO.

Input

Dòng đầu chứa số nguyên $n$ - số phần tử.
Dòng thứ hai chứa $n$ số nguyên $x_{1}, x_{2}, \dots, x_{n}$ .

Output

In $n$ dòng. Dòng thứ $i$ là YES nếu $x_{i}$ có đúng ba ước dương, ngược lại là NO.

Constraints

$1 \leq n \leq 1 0^{5}$ .
$1 \leq x_{i} \leq 1 0^{12}$ .

Scoring

Subtask $1$ ( $50%$ số điểm): $n \leq 100$ và $x_{i} \leq 1 0^{6}$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

6
4 5 9 16 25 49

Output

YES
NO
YES
NO
YES
YES

Giải thích: Các số $4, 9, 25, 49$ lần lượt là bình phương của các số nguyên tố $2, 3, 5, 7$ , nên mỗi số có ba ước. Số $5$ chỉ có hai ước, còn $16$ là bình phương của $4$ - một hợp số - nên đều nhận NO.

Phân tích: Một số có số lượng ước lẻ chỉ khi nó là số chính phương. Nếu x=p^2 với p nguyên tố, các ước của x đúng là 1,p,p^2. Ngược lại, nếu căn của x là hợp số thì còn xuất hiện thêm các ước khác. Vì vậy điều kiện cần và đủ là: x là bình phương của một số nguyên tố.
Thuật toán: Sàng nguyên tố tới 10^6. Với mỗi x, tìm căn nguyên r và hiệu chỉnh quanh giá trị sqrt; in YES khi r*r=x và r được sàng là nguyên tố.
Chứng minh đúng: Nếu thuật toán in YES, x=p^2 với p nguyên tố nên có đúng ba ước. Nếu x có đúng ba ước, số lượng ước lẻ buộc x là chính phương; căn không thể hợp số, nên là nguyên tố và thuật toán cũng in YES. Hai chiều đều đúng.
Độ phức tạp: Sàng mất O(10^6 log log 10^6); mỗi phần tử được kiểm tra trong O(1), bộ nhớ O(10^6).