- 866. 试除法判定质数(python)
- 题目
- 解法
- python代码实现
质数是指在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数。
合数是指在大于1的整数中除了能被1和本身整除外,还能被其他数(0除外)整除的数。与之相对的是质数,而1既不属于质数也不属于合数。
方法一 : 暴力破解 , 时间复杂度是 O(n)
。
方法二:由合数的约数总是成对出现,如,2
是6
的约数,6/2 = 3
,那3
也是6
的约数 。
可以得出更一般的推导式,若d|n
,令a = d|n
,则有a|n
成立。我们只枚举d <= d|n
这部分数,也就是d<=sqrt(n)
。
方法二的时间复杂度为O(sqrt(n))
,空间复杂度为O(1)
。
def judge(n):
if n <= 1:
return False
i = 2
while i <= n // i:
if n % i == 0:
return False
i += 1
return True
for _ in range(int(input())): # int(input()) 只能接受数字, 并且转换成int类型的数据
n = int(input())
print("Yes") if judge(n) else print("No")
注:
上述代码中 while i <= n // i
的循环条件,最好不要写成 while i*i<=n
,当n = 2147483647
时,此时若
i
2
≤
n
i^2 \leq n
i2≤n,但是在后面的循环中存在溢出风险。也不推荐写成while i<=sqrt(n)
,每次循环都需要求一个根号n
,计算根号比较慢。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)