在这个python素数程序中寻找反例

Question

我拼凑了这个脚本，吐出整数n的素因数分解。在脚本的最后，我将当前的素因数列表(包括多重性(相乘，并检查它是否等于n;如果没有，我把那个乘积除出来，如果它是素数，则附加商。

我已经测试了大量的数字，每次都有效，但从数学上讲，我不确定为什么。我不应该循环检查range (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)的因子。