如何用Haskell高效找出一个数的最大质因数？

我正在通过解决欧拉计划（Project Euler）的题目练习Haskell，第3题要求找出数字600851475143的最大质因数，这道题我几年前用Java做过。

我写出了以下代码：

primes :: [Int]
primes = sieve [2..]
    where sieve (p:xs) = p : sieve (filter (\x -> x `rem` p /= 0) xs)

biggestPrimeFactor :: Int -> Int
biggestPrimeFactor 1 = 0
biggestPrimeFactor x =
    if x `elem` takeWhile (< x + 1) primes
        then x
        else last (filter (\y -> x `rem` y == 0) (takeWhile (< x `div` 2) primes))

这段代码对较小的数表现很好，但效率极低，因此无法处理给定的大数。原因很明显：程序会遍历所有小于该数一半的质数（如果该数本身不是质数），但我不知道该如何优化。我希望能进一步缩小检查范围，但不知道怎么做。

请注意，我并非寻求“最优解”，而是需要一个至少对大数有中等效率、且易于理解和实现的方案，因为我还是Haskell初学者。

优化思路（适合初学者） #

这里有几个易理解、好实现的优化点，能大幅提升效率：

• 缩小检查范围到平方根：如果数n存在大于其平方根的因数，那么对应的另一个因数必然小于平方根。因此只需检查到sqrt(n)即可，若到这里还没找到因数，n本身就是质数。
• 边分解边缩小目标数：找到一个质因数后，立即将目标数除以该因数，继续分解新的目标数——这样目标数会快速变小，后续的检查范围也随之缩小。
• 替换低效操作：elem和last需要遍历整个列表，对于大数来说非常慢，换成递归逐次检查的方式更高效。
• 改用Integer类型：600851475143超出了Int的范围（Haskell中Int通常是32位，最大值约2e9），必须用支持任意精度的Integer。

优化后的代码 #

-- 保持埃氏筛的实现，初学者易理解
primes :: [Integer]
primes = sieve [2..]
    where sieve (p:xs) = p : sieve (filter (\x -> x `rem` p /= 0) xs)

biggestPrimeFactor :: Integer -> Integer
biggestPrimeFactor n = go n primes
    where
        go 1 _ = 0  -- 1没有质因数
        go num (p:ps)
            | p * p > num = num  -- 当前质数平方超过num，num本身就是质数
            | num `rem` p == 0 = go (num `div` p) (p:ps)  -- 找到因数，除以它继续检查（处理重复质因数）
            | otherwise = go num ps  -- 不是因数，检查下一个质数

代码说明 #

• 递归函数go是核心：它接受当前待分解的数num和质数列表，逐步检查每个质数：
  1. 若p*p > num，说明剩下的num无法再被更小的质数整除，它自己就是最大质因数；
  2. 若num能被p整除，就把num除以p，继续用同一个质数p检查（比如12=2*2*3，需要多次用2分解）；
  3. 若不能整除，就跳到下一个质数继续检查。

这个实现足够高效处理600851475143，同时逻辑清晰，符合Haskell初学者的认知水平。

内容的提问来源于stack exchange，提问作者Keroten