如何优化算法更快找到小于等于给定整数的最大素数？

需求说明 #

给定一个正整数，找到小于该数的最大素数，示例如下：

input 20 -> output 19
input 100 -> output 97

原有实现问题 #

提供的基础实现采用暴力试除法，遍历所有数逐个判断素性，面对大整数（比如示例中的600851475143）时运行效率很低，核心问题在于冗余检查过多。

优化方案 #

优化1：过滤偶数（性能直接提升2倍以上） #

除了2之外，所有素数都是奇数，我们可以直接跳过所有偶数的检查：

• 找素数时从小于输入的最大奇数开始，每次步长设为-2，不用逐个减1
• 素性判断时先排除偶数的情况，之后只遍历奇数作为除数，循环次数直接减半
  优化后代码：

def isPrime(x):
    if x <= 1:
        return False
    if x == 2:
        return True
    # 直接排除偶数
    if x % 2 == 0:
        return False
    # 只遍历奇数除数，步长为2
    for j in range(3, int(x**0.5) + 1, 2):
        if x % j == 0:
            return False
    return True

def findPrimeNum(num):
    if num <= 2:
        return None
    if num == 3:
        return 2
    # 从小于num的最大奇数开始遍历
    start = num - 1 if num % 2 == 0 else num - 2
    for i in range(start, 2, -2):
        if isPrime(i):
            return i
    return 2

优化2：替换为Miller-Rabin素性检验（大整数下性能提升百倍以上） #

试除法的时间复杂度是O(√n)，面对1e12以上的大整数时效率仍然很低。Miller-Rabin是素性检验算法，对于小于2^64的整数，使用固定的检验基可以做到100%准确，时间复杂度仅为O(k log³n)，k为检验轮次，大整数下性能优势极大。
优化后代码：

# 小于2^64的整数使用以下基即可保证检验结果100%正确
_MILLER_RABIN_BASES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]

def isPrime(x):
    if x < 2:
        return False
    # 小素数直接判断
    small_primes = [2,3,5,7,11,13,17,19,23,29,31,37]
    if x in small_primes:
        return True
    # 排除偶数和小素数倍数
    for p in small_primes:
        if x % p == 0:
            return False
    # 计算d和r，满足x-1 = d*2^r
    d = x - 1
    r = 0
    while d % 2 == 0:
        d //= 2
        r += 1
    # 逐基检验
    for a in _MILLER_RABIN_BASES:
        if a >= x:
            continue
        x_pow = pow(a, d, x)
        if x_pow == 1 or x_pow == x - 1:
            continue
        for _ in range(r - 1):
            x_pow = pow(x_pow, 2, x)
            if x_pow == x - 1:
                break
        else:
            return False
    return True

def findPrimeNum(num):
    if num <= 2:
        return None
    if num == 3:
        return 2
    start = num - 1 if num % 2 == 0 else num - 2
    for i in range(start, 2, -2):
        if isPrime(i):
            return i
    return 2

# 测试大整数
print(findPrimeNum(600851475143)) # 输出 600851475067

内容的提问来源于stack exchange，提问作者陳韋勳