34 lines
No EOL
759 B
Python
34 lines
No EOL
759 B
Python
import sys
|
|
|
|
def check(n):
|
|
if n < 2:
|
|
return False
|
|
if n in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37):
|
|
return True
|
|
if n % 2 == 0:
|
|
return False
|
|
d = n - 1
|
|
r = 0
|
|
while d % 2 == 0:
|
|
d //= 2
|
|
r += 1
|
|
bases = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37)
|
|
for a in bases:
|
|
x = pow(a, d, n)
|
|
if x == 1 or x == n - 1:
|
|
continue
|
|
for _ in range(r - 1):
|
|
x = pow(x, 2, n)
|
|
if x == n - 1:
|
|
break
|
|
else:
|
|
return False
|
|
return True
|
|
data = sys.stdin.read().split()
|
|
num_tests = int(data[0])
|
|
for i in range(1, num_tests + 1):
|
|
val = int(data[i])
|
|
if check(val):
|
|
print("YES")
|
|
else:
|
|
print("NO") |