质数判断代码性能优化求助：百万级数值运行卡顿问题

原代码的核心性能问题 #

1. 质数判断循环范围过大：原isPrime函数遍历从1到n的所有数，对于接近100万的数，需要执行近百万次循环——质数判断只需检查到√n即可，因为若n存在大于√n的因数，必然对应一个小于√n的因数。
2. 冗余条件判断：i % i == 0这个条件永远为真，属于完全多余的判断，浪费计算资源。
3. 不必要的因数收集：原函数收集所有因数后再判断长度，实际上只要找到一个除1和自身外的因数，就能立即判定非质数，无需遍历完所有数。
4. 质因数分解效率低下：原factors函数遍历1到n的所有数找因数，再调用低效的isPrime判断，双重冗余导致性能雪崩。

优化后的质数判断函数 #

def is_prime(n):
    # 处理特殊数值
    if n <= 1:
        return False
    if n == 2:
        return True
    # 偶数直接排除（除2外）
    if n % 2 == 0:
        return False
    # 仅遍历奇数，范围限制到√n+1
    for i in range(3, int(n**0.5) + 1, 2):
        if n % i == 0:
            return False
    return True

优化点说明 #

• 提前拦截小数值和偶数，减少后续循环次数。
• 循环仅遍历奇数，且范围压缩到√n，循环次数骤减（比如n=1e6时，原循环执行1e6次，优化后仅执行约500次）。
• 找到因数立即返回，无需完成全部循环。

优化后的质因数分解函数 #

如果目标是获取n的所有质因数，无需先找所有因数再判断质数，直接分解更高效：

def prime_factors(n):
    factors = []
    # 先提取所有2的因数
    while n % 2 == 0:
        factors.append(2)
        n = n // 2
    # 再提取奇数因数，从3开始到√n
    i = 3
    while i * i <= n:
        while n % i == 0:
            factors.append(i)
            n = n // i
        i += 2
    # 若剩余n是大于2的质数
    if n > 2:
        factors.append(n)
    # 输出去重后的质因数
    for p in sorted(set(factors)):
        print(p)

优化点说明 #

• 直接从最小质数开始分解，避免遍历所有数的冗余操作。
• 每次分解后缩小n的范围，进一步减少循环次数。
• 天然只处理质因数，无需额外调用质数判断函数。

原factors函数的适配优化（保留原逻辑） #

如果坚持先找所有因数再筛选质数，可以通过缓存避免重复计算：

# 用字典缓存已判断过的质数结果
prime_cache = {}

def is_prime_cached(n):
    if n in prime_cache:
        return prime_cache[n]
    # 复用优化后的质数判断逻辑
    if n <= 1:
        result = False
    elif n == 2:
        result = True
    elif n % 2 == 0:
        result = False
    else:
        result = True
        for i in range(3, int(n**0.5) + 1, 2):
            if n % i == 0:
                result = False
                break
    prime_cache[n] = result
    return result

def factors_optimized(n):
    # 因数成对出现，只需遍历到√n
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            if is_prime_cached(i):
                print(i)
            # 处理成对的另一个因数，避免重复输出
            counterpart = n // i
            if counterpart != i and is_prime_cached(counterpart):
                print(counterpart)

内容的提问来源于stack exchange，提问作者coda99