挑战每日打卡python基础题
come with me !

今日练习：判断一个自然数是否是素数（质数）

素数（质数）的定义：
一个大于1的自然数，如果除了1和它本身以外，没有其他正因数，则称为素数（或质数）。例如，2、3、5、7、11等是素数，而4、6、8、9等不是素数。

方案一：

def is_prime_fast(a):
    if a <= 1:
        return False
    y = 2
    while y * y <= a:    # 相比较而言，while y <= a:  优化循环条件，检查到sqrt(a)
        if a % y == 0:
            return False
        y += 1
    return True

优化：将 while y <= a ，优化成 while y * y <= a

数学证明

为了更严谨，我们可以用数学归纳法证明：

命题：对于任何整数a > 1，如果a不是质数，那么它有一个因数b满足b <= sqrt(a)。

证明：
假设a不是质数，那么存在两个整数b和c，b >= 2，c >= 2，使得a = b * c。
假设b > sqrt(a)且c > sqrt(a)：
那么b * c > sqrt(a) * sqrt(a) = a。
但b * c = a，矛盾。
因此，至少有一个因数（b或c）满足<= sqrt(a)。

性能比较

对于a = 1000000：

while y <= a ：需要约100万次循环。
while y * y <= a：最多需要约1000次循环。

其他应用
这种优化不仅用于质数检查，还用于：

因数分解：寻找所有因数时，只需检查到sqrt(a)。
完美平方检查：判断a是否为完全平方数，可以检查int(sqrt(a)) ** 2 == a。

方案二升级版：

# 输入一个自然数，判断是否是质因数

def prime(a):
    if a <= 1:
        return False
    if a == 2:
        return False
    if a % 2 == 0:   # 除2以外，所有的偶数都有因子
        return True

    y = 3
    while y**y <= a:
        while a % y == 0:
            return True
        y += 2     #如果一个数能被最小的质因数 3,5,7整除，再进行循环
    return False

a = int(input("请输入一个自然数："))
print(prime(a))

进一步，减少循环判断

跳过偶数：除了2，所有偶数都不是素数，因此可以跳过对偶数的检查；
此外，针对奇数，可以先判断被最小的质因数 3,5,7整除，再进行循环。
即检查步长设为2（即检查3, 5, 7, ...）。