MATLAB的factor（）函數後面會發生什麼？

Question

主要是，它爲什麼如此之快（對於大數字）？該文件只告訴我如何使用它。例如，最多需要一秒才能找到1234567890987654的最大素數因子，對我而言，這看起來很瘋狂。

>>max(factor(1234567890987654)) 

ans = 

    69444443 

Answer 1

最大因子被嘗試在這種情況下的sqrt（N），或35136418。即使是最基本的優化，也會跳過所有偶數> 2，只剩下17568209個候選者進行測試。一旦找到候選17777778（和它的輔助因子69444443），該算法就足夠明智地停下來。

這可以通過修改篩進一步略微改進以跳過多個小素數2,3,5 [，7]。

基本上，即使sqrt（N）優化對於提到的性能也足夠了，除非您正在使用特殊的舊CPU（8086）。

Answer 2

查看factor和primes函數的源代碼很有意思。

factor(N) essentiallty要求primes找出所有素數達sqrt(N)。一旦他們被識別出來，它就會逐個測試他們，看他們是否劃分N。

primes(n)使用Eratosthenes' sieve：對於每個標識的素數，刪除其所有倍數exploiting sqrt again以降低複雜性。