contest: Codeforces Round #142 (Div. 2), problem: (B) T-primes

 

1. import math
2. prime = [True for i in range(10**6+1)]
3. def SieveOfEratosthenes(n):
4. p = 2
5. while (p * p <= n):
6. if (prime[p] == True):
7. for i in range(p * p, n+1, p):
8. prime[i] = False
9. p += 1
10. if __name__=='__main__':
11. n = input()
12. inp = list(map (int,input().split()))
13. SieveOfEratosthenes(int(math.sqrt(max(inp))))
14. for i in range(len(inp)):
15. if inp[i] == 1:
16. print("NO")
17. continue
18. if int(math.sqrt(inp[i]))**2 == inp[i] and prime[int(math.sqrt(inp[i]))]:
19. print("YES")
20. else:
21. print("NO")