Haskell中基于无限素数列表的prime_factors函数运行不终止问题求解

• primes是惰性求值的无限素数列表，原始的prime_factors函数没有给遍历的素数x设置上限，程序会持续生成更大的素数并逐一验证是否能整除n，永远不会自动停止遍历。
• 大于n的素数不可能整除n，但原始代码没有加入这个终止判断，导致得到所有符合条件的素因数后，程序仍在无意义地遍历后续无限素数序列。

你给出的参考代码中使用的x*2 <= n约束存在缺陷，会漏掉n本身是素数的场景，正确的修改方式是给列表推导增加x <= n的上限约束：素因数的最大取值不可能超过n本身，当生成的素数大于n时，程序就会终止遍历。
修改后的完整可运行代码如下：

primes :: [Integer] 
primes = f [2..] 
  where 
    f (p:xs) = p : f [x | x <- xs, x `mod` p /= 0]
    f [] = []

prime_factors :: Integer -> [Integer]
prime_factors n = [x | x <- primes, x <= n, n `mod` x == 0]

如果需要更高的执行效率，也可以将上限缩小到√n优化遍历逻辑：如果遍历完所有小于等于√n的素数后剩余的n值大于1，说明剩余值本身就是一个素因数，优化版本实现如下：

prime_factors :: Integer -> [Integer]
prime_factors n = factor n primes
  where
    factor 1 _ = []
    factor m (p:ps)
      | p * p > m = [m]
      | m `mod` p == 0 = p : factor (m `div` p) (p:ps)
      | otherwise = factor m ps

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