Haskell中的主要因素

Question

我是Haskell的新手.

如何生成包含下一个整数的素因子的列表列表？

现在我只知道如何生成素数:

primes = map head $ iterate (\(x:xs) -> [y | y<-xs, y `mod` x /= 0 ]) [2..]

Answer 1

确定主要因素的简单方法n是

• 搜索第一因子d在[2..n-1]
• 如果D存在:返回 d : primeFactors(div n d)
• 否则返回n(因为n是素数)

码:

prime_factors :: Int -> [Int]

prime_factors 1 = []
prime_factors n
  | factors == []  = [n]
  | otherwise = factors ++ prime_factors (n `div` (head factors))
  where factors = take 1 $ filter (\x -> (n `mod` x) == 0) [2 .. n-1]

这显然可以使用大量优化(仅搜索从2到sqrt(N),缓存到目前为止找到的素数并仅为这些等计算除法等)

UPDATE

使用案例略微修改的版本(由@ user5402建议):

prime_factors n =
  case factors of
    [] -> [n]
    _  -> factors ++ prime_factors (n `div` (head factors))
  where factors = take 1 $ filter (\x -> (n `mod` x) == 0) [2 .. n-1]

Answer 2

这是一个性能良好且易于理解的实现，其中isPrime和primes是递归定义的，primes默认情况下会被缓存。primeFactors定义只是对 的正确使用primes，结果将包含连续重复的数字，此功能可以轻松计算每个因子的数量，(map (head &&& length) . group)并且可以轻松通过 将其唯一化(map head . group)：

isPrime :: Int -> Bool
primes :: [Int]

isPrime n | n < 2 = False
isPrime n = all (\p -> n `mod` p /= 0) . takeWhile ((<= n) . (^ 2)) $ primes
primes = 2 : filter isPrime [3..]

primeFactors :: Int -> [Int]
primeFactors n = iter n primes where
    iter n (p:_) | n < p^2 = [n | n > 1]
    iter n ps@(p:ps') =
        let (d, r) = n `divMod` p
        in if r == 0 then p : iter d ps else iter n ps'

以及用法：

> import Data.List
> import Control.Arrow

> primeFactors 12312
[2,2,2,3,3,3,3,19]

> (map (head &&& length) . group) (primeFactors 12312)
[(2,3),(3,4),(19,1)]

> (map head . group) (primeFactors 12312)
[2,3,19]

Answer 3

直到股息m<2,

1. n从素数中取第一个除数.
2. 重复将m通过n同时整除.
3. n从素数中取下一个除数,然后转到2.

实际使用的所有除数列表是原始的因子m.

码:

-- | prime factors
--
-- >>> factors 13
-- [13]
-- >>> factors 16
-- [2,2,2,2]
-- >>> factors 60
-- [2,2,3,5]
--
factors :: Int -> [Int]
factors m = f m (head primes) (tail primes) where
  f m n ns
    | m < 2 = []
    | m `mod` n == 0 = n : f (m `div` n) n ns
    | otherwise = f m (head ns) (tail ns)

-- | primes
--
-- >>> take 10 primes
-- [2,3,5,7,11,13,17,19,23,29]
--
primes :: [Int]
primes = f [2..] where f (p : ns) = p : f [n | n <- ns, n `mod` p /= 0]

更新:

此替换代码通过避免不必要的评估来提高性能:

factors m = f m (head primes) (tail primes) where
  f m n ns
    | m < 2 = []
    | m < n ^ 2 = [m]   -- stop early
    | m `mod` n == 0 = n : f (m `div` n) n ns
    | otherwise = f m (head ns) (tail ns)

primes如Will Ness的评论所述,也可以大幅加速:

primes = 2 : filter (\n-> head (factors n) == n) [3,5..]