Простая факторизация с использованием списка понимания
Я хочу найти все основные факторы данного числа, используя только метод понимания списка и / или .
(оператор композиции функций) в Haskell. Я специально хочу избежать рекурсивного решения.
Например, pfactors 120
должен производить [2,2,2,3,5]
выход.
Я старался:
pfactors n = [p | p <- [2..n], n `mod` p == 0, [d | d <- [1..p], p `mod` d == 0] == [1,p]]
Но когда я звоню pfactors 120
результат [2,3,5]
не все главные факторы.
1 ответ
Вот как я это сделаю:
pfactors :: Integer -> [Integer]
pfactors n = [ p
| p <- [2..n] -- Possible factors
, [d | d <- [1..p], p `mod` d == 0] == [1,p] -- Are prime
, _ <- [ p | i <- [1..n], n `mod` p^i == 0] ] -- Divisible powers
По сути, это решение, которое у вас есть, но разница в том, что в конце у него есть дополнительное понимание списка, которое содержит столько элементов, сколько p
факторы в n
,
Отказ от ответственности Я действительно не буду делать это так на самом деле.
РЕДАКТИРОВАТЬ Я чувствовал себя грязно писать выше, так что для справки, это что-то ближе к тому, что я бы написал:
pfactors' :: Int -> [Int]
pfactors' = unfoldr firstFactor
where
firstFactor n =
listToMaybe [(f, n `div` f)
| f <- [2..n]
, n `mod` f == 0]
зависимости: Data.List (unfoldr)
, Data.Maybe (listToMaybe)