参考作者:冰中月
题目:
给定 n个正整数 ai,判定每个数是否是质数。
输入格式:
第一行包含整数 n。接下来 n 行,每行包含一个正整数 ai。
输出格式
共 n行,其中第 i行输出第 i个正整数 ai是否为质数,是则输出 Yes,否则输出 No。
数据范围
1 ≤ n ≤ 100 , 1 ≤ ai ≤ 231−1
输入样例:
2
2
6
输出样例:
Yes
No
N的因数只需从2枚举到N的1/2次方
所以代码时间复杂度可以变为O(N的1/2次方)
Python代码:
N=110
n=int(input())
def xea (x):
i=2
while i <= x//i :
if x % i ==0:
return 'No'
i+=1
return 'Yes'
for i in range(n):
a=int(input())
if a<2:
print('No')
else:
print(xea(a))
N=110
n=int(input())
for i in range(n):
a=int(input())
if a<2:
print('No')
else:
print(xea(a))