T-Prime
Submit solution
Points:
2
Time limit:
1.0s
Memory limit:
98M
Author:
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG
Số nguyên tố là một số nguyên dương chỉ có đúng 2 ước. Tương tự đó, ta gọi số nguyên dương t là T-prime khi số đó chỉ có đúng 3 ước.
Bạn được cung cấp một mảng gồm n số nguyên dương. Với mỗi phần tử bạn hãy kiểm tra xem nó có phải là số T-prime hay không.
Input
- Dòng đầu tiên là một số nguyên dương n \((1 \le n \le 10 ^ 5)\) là số phần tử của mảng
Dòng tiếp theo gồm n số nguyên dương x[i] ngăn cách bởi dấu cách \((1 \le x[i] \le 10^{12})\)
Output
- Gồm n dòng: mỗi dòng là kết quả của việc kiểm tra. "YES" nếu đó là số T-prime, "NO" là ngược lại
Examples Input
3
4 5 6
Output
YES
NO
NO
Note The given test has three numbers. The first number 4 has exactly three divisors — 1, 2 and 4, thus the answer for this number is "YES". The second number 5 has two divisors (1 and 5), and the third number 6 has four divisors (1, 2, 3, 6), hence the answer for them is "NO".
Comments
Bình Phương Số Nguyên Tố
Bài này để kiểm tra nhanh mình có thể dùng pp sàng Eratosthene lọc các snt tới 10^6, từ đó xác định được tất cả các T-prime từ 1 tới 10^12 (bình phương snt).