Python 素数判断与查找算法详解

Python 素数判断与查找算法详解

素数（质数）是指在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的自然数。在编程中，素数判定是常见的算法练习，不同的实现方式对性能有显著影响。

判断素数

第一种：暴力解法

普通查找：遍历 2 到 n-1 的值，找出是否存在因数。时间复杂度为 $O(n)$。

def IsPrime1(num):
    if num == 2 or num == 3:
        return True
    else:
        for i in range(2, num):
            if num % i == 0:
                return False
        return True

第二种：开方优化

如果一个自然数是非素数，那么它的所有因数中，必存在某个因数小于等于其平方根。因此只需遍历 2 到 $√{n}$。时间复杂度降为 $O(√{n})$。

import math

def IsPrime2(num):
    if num == 2 or num == 3:
        return True
    n = int(math.sqrt(num))
    for i in range(2, n + 1):
        if num % i == 0:
            return False
    return True