Реализация метода факторизации в Haskell

Question

я делаю вопрос 266 в Project Euler и после небольшого поиска нашел Этот метод быстро находить множители числа.Что вам нужно сделать, так это найти все перестановки простых множителей числа:это его факторы.

У меня уже есть модуль для поиска простых коэффициентов мощности числа, например:

Main> primePowerFactors 196
[(2,2),(7,2)]

Это в основном показывает, что: 2^2 * 7^2 == 196.Отсюда я хочу найти все перестановки этих степеней, чтобы получить множители 196 следующим образом:

• (2^0)(7^0) = 1
• (2^1)(7^0) = 2
• (2^2)(7^0) = 4
• (2^0)(7^1) = 7
• (2^1)(7^1) = 14
• (2^2)(7^1) = 28
• (2^0)(7^2) = 49
• (2^1)(7^2) = 98

Я придумал следующее:

factors n = [a|a<-map facs (primePowerFactors n), y <- [0..(snd $ last $ primePowerFactors n)]]
 where 
  facs (x,y) = (x,y)   
rSq n = toInteger $ round $ sqrt (fromInteger n)    
psr n = last $ dropWhile (<= rSq n) $ factors n
p = foldl' (*) 1 $ takeWhile (< 190) primes
answer = (psr p) `mod` (10^16)

Но моя проблема в том, что factors не работает должным образом.Я хочу, чтобы он перебрал все возможные значения показателя степени для каждого простого множителя, а затем нашел произведение, дающее этот множитель.Как его можно изменить, чтобы вернуть только факторы н?

Answer 1

для некоторого кода гольфа я написал хорошую функцию установки мощности, которая довольно проста.

powerSet [] = []
powerSet (x:xs) = xs : map (x:) (powerSet xs) ++ (powerSet xs)

Недостатком этого алгоритма является то, что он не включает исходный набор, однако он идеально подходит для вас, поскольку не выглядит так, как вам нужно.

объедините это с возможностью конвертировать ваши primePowerFactors n в список целых чисел, скажем

ppfToList = concatMap (\(x,y)->replicate y x)

с помощью этих помощников генерируется список факторов из числа n с помощью

factors n = nub . map product . powerSet . ppfToList . primePowerFactors $ n
-- will be out of order, you can add a call to `sort` to fix that

Этот тип алгоритма, вероятно, немного сложнее выразить с точки зрения понимания списка.

Answer 2

Прежде всего, facs это тождественная функция:

facs (x,y) = (x,y)

А y привязан к шаблону с левой стороны, хотя вы, вероятно, предполагали, что это будет y из понимания списка.Имена переменных, связанные с пониманием списка, являются локальными для этого понимания и не могут использоваться в другой области, например where пункт.

Так же y в понимании списка вычисляется только из последней экспоненты факторов:

y <- [0..(snd $ last $ primePowerFactors n)]

Для каждого фактора следует учитывать свой показатель степени, а не только показатель степени последнего фактора.

Более фундаментальная проблема заключается в том, что тип возвращаемого значения factors функция, похоже, не соответствует своему назначению:

*Euler> :t factors
factors :: Integer -> [(Integer, Int)]

Это возвращает список степеней простых множителей, в то время как он должен создать список этих конструкций, например:

[
   [(2,0), (7,0)],
   [(2,1), (7,0)],
   [(2,2), (7,0)],
   [(2,0), (7,1)],
   [(2,1), (7,1)],
   ...
]

Требуется простая факторизация всех возможных факторов, но функция, похоже, возвращает только одну простую факторизацию.