python - 在这个 python 质因数程序中寻找反例

Question

我拼凑了这个脚本来输出整数n的质因数分解。在脚本的最后，我将当前的质因数列表(包括重数)相乘，并检查其是否等于 n；如果不是，我将该乘积除掉并附加商(如果它是素数)。

我测试了大量的数字，每次都有效，但从数学上讲我不确定为什么。我是否应该循环检查范围 (sqrt(n), n) 中剩余的素数？在这个范围内不可能有一个包含两个素数的整数吗？如果有的话，我还没有找到例子。我是Python新手，所以另一个解释是我不理解我自己的代码，以及它以某种方式为我循环。

from math import sqrt
n = int(input("Let's factor a number:"))

def isPrime(x):
    for i in range(2,int(sqrt(x)+1)):
        if x%i==0:
            return False
    return True

m = int(sqrt(n)+1)
i = 1
factors = []
while(1 < m):
    if (n % (m**i) == 0 and isPrime(m) == True):
        factors.append(m)
    else:
        m -= 1
        i = 1
        continue
    i += 1

prod = 1
for i in factors:
    prod *= i

if prod == n:
    print(factors)
elif isPrime(n/prod) == True:
    factors.append(int(n/prod))
    print(factors)

Answer 1

不，你不需要这样的循环。 n 只能有一个质因数 > sqrt(n)。假设相反:至少有两个。 i, j > sqrt(n)。在这种情况下，i*j 必须 > sqrt(n)*sqrt(n)，这就是你的矛盾。

找到小于 sqrt(n) 的所有因数后，剩余的量都是质数，并且是唯一大于 sqrt(n) 的因数。