Python 判断一个数是不是质数

一般我们会这样写

# 判断是不是质数
def isZhi(a):
    for i in range(2, a):
        if a % i == 0:
            return False;
        else:
            continue;
    return True

算法优化

# 判断是不是质数
def isZhi(a):
    for i in range(2, int(math.sqrt(a))+1):
        if a % i == 0:
            return False;
        else:
            continue;
    return True

为什么判断到 int(math.sqrt(a))+1 就可以停止了呢？我们来举个栗子

比如 4 这个数字，根号4 = 2，也就是2 * 2 = 4 那就证明除了 1 和 4 本身还有 2 这个数能够被 4 整除

再举个栗子，6这个数字，根号6 = 2.449… 转化为 Int 就是 2， 再加 1 就是 3，但是 range 取不到 3 ，也就是取到 2 ，那我们就判断 1,2，到 2 的时候他就不是质数了

再举个例子 9这个数，根号 9 是不是等于 3 ，那我们就判断 1,2,3这3个数，判断到3就停止了（不是质数），后面的数就不用判断了