在Haskell中实现因式分解法 [英] Implementing a factorisation method in Haskell

问题描述

我在欧拉项目中做问题266 ，之后一点搜索，发现这种方法快速查找数字的因素。你所做的是找到一个数字的主要因素的所有排列：这些都是它的因素。

我已经有一个模块来查找数字的主要功率因子，例如：

  Main> primePowerFactors 196 
 [（2,2），（7,2）] 
  

这是基本上显示： 2 ^ 2 * 7 ^ 2 == 196 。从这里我想找到所有这些权力的排列，给予这些因素196：
$ b

• （2 ^ 0）（7 （2 ^ 2）（7 ^ 0）= 1美元b $ b（2 ^ 1）（7 ^ 0）= 2
  ^ （2 ^ 0）（7 ^ 1）= 7
  （2 ^ 1）（7 ^ 1）= 14
>
（2 ^ 2）（7 ^ 1）= 28
li（2 ^ 0）（7 ^ 2）= 49

• （2 ^ 1）（7 ^ 2）= 98

我想出了以下内容：

 因子n = [a | a <-map facs（primePowerFactors n），y < -  [0 ..（snd $ last $ primePowerFactors n）]] 
其中
 facs（x，y）=（x，y）
 rSq n = toInteger $ round $ sqrt（fromInteger n）
 psr n = last $ （<= rSq n）$因子n 
p = foldl'（*）1 $ takeWhile（<190）素数
 answer =（psr p）`mod`（10 ^ 16）
  

但是我的问题是因子不起作用正常。我希望它通过每个主要因素的指数的所有可能值进行置换，然后找到产品给出该因子。如何修改它以返回 n 的因素？

？

解决方案

  powerSet [] = [] 
 powerSet（x： xs）= xs：map（x :)（powerSet xs）++（powerSet xs）
  

A这个算法的缺点是它不包含原始的集合，但是这对你来说是完美的，因为它看起来不像你想要的。

一种将 primePowerFactors n 转换为整数列表的方法，可以说

  ppfToList = concatMap（\（x，y） - > replicate yx）
  

帮助者中，由数字n生成的因子列表是由

 因子n = nub生成的。地图产品。 powerSet。 ppfToList。 primePowerFactors $ n 
  - 将无法使用，您可以添加对`sort`的调用以修复
  

这种算法在列表理解方面可能有点难以表达。

I am doing question 266 at Project Euler and after a bit of searching, found this method of quickly finding the factors of a number. What you do is find all the permutations of the prime factors of a number: these are its factors.

I already have a module to find the prime power factors of a number, eg:

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

This is basically showing that: 2^2 * 7^2 == 196. From here I want to find all the permutations of those powers, to give the factors of 196 thusly:

• (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

I came up with the following:

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)

But my problem is that factors doesn't work properly. I want it to permute through all the possible values of the exponent for each prime factor and then find the product to give the factor. How can it be modified to return the just the factors of n?

解决方案

for some code golf i wrote a nice power set function that is pretty simple.

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

A deficiency of this algorithm is that it doesn't include the original set, however that is perfect for you since it doesn't look like you want it.

combine this with a way to convert your primePowerFactors n into a list of ints, lets say

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

using these helpers, a list of factors from a number n is generated with

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

This sort of algorithm is probably a bit harder to express in terms of a list comprehension.

这篇关于在Haskell中实现因式分解法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！