Python列表索引越界问题及大数600851475143质因数分解优化

我正在编写代码分解数字600851475143的质因数（我的老师肯定是针对我们）。代码运行到位置10007时一切正常，甚至输出了质数71和6857，但之后出现了如下错误。

我的代码：

numero = 600851475143 #number
primos = [2,...,104729] # here is a list of 10000 primes that stackoverflow wouldn't let me insert
# ^ primes
ponteiro = 0 # pointer
cont = primos[0]
primos_usados = [] #used primes
while True:
    print(f"{ponteiro} - {cont}    {numero}\n{primos_usados}") # to see the values ​​per loop
    if(numero%primos[cont] == 0):
        numero = numero/primos[cont]
        primos_usados.append(primos[cont])
        ponteiro = 0
        if(numero/primos[cont] == 1):
            break
    ponteiro += 1
    cont = primos[ponteiro]

错误信息：

if(numero%primos[cont] == 0):
IndexError: list index out of range

我尝试手动访问primos[9999]时也出现了相同错误。如何在避免该错误的同时，无需手动输入10000个质数？

先揪出代码的核心问题 #

你犯了一个逻辑错误：把质数的值cont当成了列表索引去访问primos[cont]。比如cont是71时，你实际在取primos[71]；当cont变成6857时，这个索引远超过列表最大索引9999，直接触发越界。这完全混淆了「质数数值」和「列表索引」两个概念。

无需手动输入质数的解决方案 #

根本不用预先存一堆质数，直接动态试除就行，下面两种方案任选：

方案1：基础版试除法（简单易懂）

从2开始逐个试除，直到剩余数为1：

numero = 600851475143
primos_usados = []
divisor = 2

while numero > 1:
    # 只要能整除，就反复用当前除数分解
    while numero % divisor == 0:
        primos_usados.append(divisor)
        numero = numero // divisor  # 用整数除法避免浮点数问题
    # 不能整除就换下一个除数
    divisor += 1

print("质因数列表:", primos_usados)
print("最大质因数:", primos_usados[-1])

方案2：优化版试除法（效率更高）

针对大数优化，只试除到剩余数的平方根，且跳过偶数：

import math

numero = 600851475143
primos_usados = []

# 先单独处理偶数情况
while numero % 2 == 0:
    primos_usados.append(2)
    numero = numero // 2

# 从3开始只试除奇数
divisor = 3
# 试除到剩余数的平方根即可
while divisor <= math.isqrt(numero):
    while numero % divisor == 0:
        primos_usados.append(divisor)
        numero = numero // divisor
    divisor += 2

# 如果最后剩余的数大于1，说明它本身就是一个质因数
if numero > 1:
    primos_usados.append(numero)

print("质因数列表:", primos_usados)
print("最大质因数:", primos_usados[-1])

优化版的效率优势 #

• 单独处理2，之后只试除奇数，直接减少一半循环次数。
• 试除范围限定在剩余数的平方根以内：如果一个数有大于其平方根的因数，对应的另一个因数必然小于平方根，已经被试除过了，无需重复判断。

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