这个最大质因数的查找算法是怎么用的？

Question

我在网上看到这个YouTube视频，这个家伙用一个看似简单的方法找到了一个数字的最大质因数，但我不太明白其中的数学原理。下面是链接 https:/m.youtube.comwatch?v=5kv9q7qgvlI。代码--

n=1234 # Some number whose largest factor I want to find
i=2 # It seems that he tries to start from the smallest prime number
while i**2<n: # I don't understand this part where he checks if the square of variable is less than the target number 
    while n%i==0: # I know this checks if n is divisible by i
        n/=i 
    i+=1 # increments i's value
print(n) 

我知道这段代码是可行的，但为什么？我得到了最后两行，但为什么要检查变量i的平方是否小于n？

Answer 1

如果你的数字 N 可除以 I (换句话说。I 是一个因素 N)，以及 I 大于 sqrt(N)那么，一定还有另一个因素 N，叫它 J = N/I小于 sqrt(N).

如果你穷尽所有的潜在因素，直至。I你一定已经找到了 J所以你前面已经讲到了这个因式化。

我们要找的是最大的 首要的 的因素，所以问题仍然是最后的 N 当终止循环的时候是一个质数。

每当我们遇到一个因数为 N，我们把 N 由这个因素，所以当考虑一个潜在的因素时。I我们可以肯定，当前的 N 不会有任何因素低于 I 更多。

最后能不能 N 当终止循环时，是由一个以上的因子组成的（即不是质数）？

不可以，如果N不是质数，那么它必须由多个因子组成（即不是质数）？

如果N不是质数，它必须由以下因子组成 K 和 L (N = K * L)，以及 K 和 L 既要大于 sqrt(N)否则，我们会除以 K 或 L 在前面的步骤中。但将两个大于 sqrt(N)，将永远大于 N违反 N = K * L.

所以，假设最后的 N 不是质数，遇到了矛盾，因此我们可以肯定，最后的 N 是原来的系数 N而这个因数确实是一个质数。

原代码的注意事项(感谢JohanC):

原代码检查： I 严格小于 SQRT(N) (while i**2<n). 这将会错过像N=9这样的情况，在这种情况下，它的平方根3必须被包含在迭代中。所以，这里应该改为 while i**2<=n.

而且代码有可能出现一些不准确的地方。

• 使用浮点除法 (/= 操作员而不是 //=)可能会给出不准确的结果。这适用于Python，而在Java等语言中。/= 就可以了。
• 在 Python 中，将一个整数提高到 2 的幂 (while i**2<=n)似乎可以保证精确的整数运算，所以在Python上下文中是可以的。在像 Java 这样的语言中，我建议不要使用 pow() 函数，因为该函数通常使用浮点算术，有可能出现不精确的结果，但只需写下 i*i.