The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
最大质因数
13195 的质因数包括 5、7、13 和 29。
600851475143 的最大质因数是多少？
由于 600851475143 并不是一个很大的数，我们可以考虑从 2 开始暴力求取：
(named-let f ((i 2) (num 600851475143))
(cond
((= i num) i)
((zerop (% num i))
(f i (/ num i)))
(t (f (+ i 1) num))))
;; 6857由于除 2 外的所有质数都是奇数，当我们用过 2 后，我们可以从 3 开始并将步长取 2 而不是 1，理论上这比上面的代码快两倍。由于一眼可以看出这个数字不是偶数，我们直接从 3 开始：
(named-let f ((i 3) (num 600851475143))
(cond
((= i num) i)
((zerop (% num i))
(f i (/ num i)))
(t (f (+ i 2) num))))
另一个优化是：我们不需要从 3 开始一直取到 num，这是因为 num 的因数不可能大于 sqrt(num) ，我们可以为除数设置一个限制，当除数大于该值时就说明该数为质数：
(named-let f ((i 3)
(num 600851475143)
(range (floor (sqrt 600851475143))))
(cond
((> i range) num)
((zerop (% num i))
(f i (/ num i) (floor (sqrt (/ num i)))))
(t (f (+ i 2) num range))))这个问题本质上就是求取某个数字的所有质因数，只不过题目只要求最大的质因数。