866. 试除法判定质数

866. 试除法判定质数(python)

文章目录

• 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)。

python代码实现

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，计算根号比较慢。