python中的整数因式分解

Question

我在这个网站上看到了很多用python进行整数因式分解的方法，但并不真正理解它们，所以我尝试用我自己的方式来做：

def factorisation(n):
fact = []
i = 2
while i<=n:     
    if n%i==0:      
        fact.append(i)
        n//= i
    else:
        i+=1
return fact

我认为它是有效的，但我真的不知道为什么while循环从I到n。。。从我的课上我学到了，如果从2到sqrt（n），我们必须这样做。 我误解什么了吗？ 我能改进一下吗？ 谢谢：）

Answer 1

如果要寻找最小的因子（例如在素性测试中），只需要转到floor（sqrt（n））。如果你想要所有的因素，那么你应该检查从0到n/2。在

简而言之：

素性：

n = int(input('Please input a number: ')
sn = int(sqrt(n))
for x in range(2,sn+1):
    if n%x == 0:
        print('Not prime. Divisible by: '+str(x))
print(str(n)+' is prime')

因子分解：

^{pr2}$

我希望这能帮助你理解。在

Answer 2

当一个整数n不能被sqrt(n)的任何数整除，这就足以表明n是素数。在这种情况下，除了n本身之外，您不会找到任何其他因素。在

所以您可以做的是在sqrt(n)处停止循环，并将n的剩余值添加到素数因子列表中。在