logo标签列表

Haskell中的质因数

haskellprimesfactorizationprime-factoring
17

我是Haskell的新手。

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

目前，我只知道如何生成质数：

primes = map head $ iterate (\(x:xs) -> [y | y<-xs, y `mod` x /= 0 ]) [2..]
你进展到哪一步了？例如，您可以尝试编写一个将单个数字分解质因数的函数。 - GS - Apologise to Monica
8个回答
21

确定一个正整数 n 的质因数的简单方法是：

  • 在区间 [2..n-1] 中查找第一个除数 d
  • 如果存在 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)搜索，缓存迄今为止找到的质数，并仅针对这些计算除法等）。

更新

稍微修改后的版本使用了case（如@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]
3
请注意，foo == [] 在 foo 的类型中引入了一个 Eq 约束（实际上在这里不需要），而 case foo of [] -> ... 则没有引入约束。 - d8d0d65b3f7cf42
2
使用守卫的另一种替代方案是仅使用 null factors，而不是 factors == []。 - bheklilr
1
不需要检查所有的[2..n-1]数字。你只需要检查所有的[2..sqrt(n)]，因为如果p | n，则p <= sqrt(n)。 - d12frosted
@RottenBrain 我知道（我在我的答案中提到了它作为可能的优化）- 我不想破坏 OP 的乐趣 :-) - Frank Schmitt
@Frank Schmitt，哦，抱歉。您确实提到了这个优化 :) - d12frosted
显示剩余11条评论
6

在除数 m 小于 2 之前，

  1. 从质数中选择第一个除数 n。
  2. 当可以整除时，重复用 n 除以 m。
  3. 从质数中选择下一个除数 n，并回到第二步。

实际使用的所有除数列表是原始 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..]
1
这段代码运行速度慢了两倍：在因子中它没有停在sqrt处，在质数中它也没有等到质数的平方根。 - Will Ness
1
感谢您的建议，我得以更新代码。 只添加了一个保护条件，这段代码就显著地提高了速度。 原始代码需要 15 秒才能分解 599946，而更新后的代码仅需 6 毫秒。 - Hironobu Nagaya
1
太好了，你已经改进了 factors 但是 primes 的速度仍然太慢了。将你的定义速度与 2:filter (\n-> head (factors n) == ...... 进行比较（完成定义）。 :) 你能找到速度差异的原因吗？另请参见 "empirical orders of growth"。 - Will Ness
@WillNess 我理解你的意图，但我无法完成你的代码片段。很抱歉，你能给我展示一下你定义的“primes”吗？ - Hironobu Nagaya
3
当然，它是primes = 2：filter（\ n-> head（factors n）== n）[3,5 ..]。 :) - Will Ness
6

这是一个表现优异且易于理解的实现，其中 isPrime 和 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]
3
我刚刚处理了这个问题，这是我的解决方案。
两个辅助函数如下：
factors n = [x | x <- [1..n], mod n x == 0]
isPrime n = factors n == [1,n]

然后使用列表推导式获取所有质因数以及它们的个数。
prime_factors num = [(last $ takeWhile (\n -> (x^n) `elem` (factors num)) [1..], x) | x <- filter isPrime $ factors num]

在哪里

x <- filter isPrime $ factors num

告诉我给定数字的质因数，并且...
last $ takeWhile (\n -> (x^n) `elem` (factors num)) [1..]

告诉我这个因素的数量。 示例 
> prime_factors 36    -- 36 = 4 * 9
[(2,2),(2,3)]

> prime_factors 1800  -- 1800 = 8 * 9 * 25
[(3,2),(2,3),(2,5)]
3

Haskell允许您创建无限互递归的列表。让我们利用这个特性。

首先，让我们创建一个帮助函数，它可以尽可能地将一个数字除以另一个数字。一旦我们找到一个因子，我们将需要它来完全从数字中消除它。

import Data.Maybe (mapMaybe)

-- Divide the first argument as many times as possible by the second one.
divFully :: Integer -> Integer -> Integer
divFully n q | n `mod` q == 0   = divFully (n `div` q) q
             | otherwise        = n

接下来，假设我们已经有了所有质数的列表，我们可以通过将该数字除以小于该数字平方根的所有质数来轻松找到一个数字的因子，并且如果该数字可被整除，则记录该质数。
-- | A lazy infinite list of non-trivial factors of all numbers.
factors :: [(Integer, [Integer])]
factors = (1, []) : (2, [2]) : map (\n -> (n, divisors primes n)) [3..]
  where
    divisors :: [Integer] -> Integer -> [Integer]
    divisors _ 1          = []   -- no more divisors
    divisors (p:ps) n
        | p^2 > n       = [n]  -- no more divisors, `n` must be prime
        | n' < n        = p : divisors ps n'    -- divides
        | otherwise     = divisors ps n'        -- doesn't divide
      where
        n' = divFully n p

相反地，当我们拥有所有数字因子的列表时，很容易找到质数：它们恰好是那些唯一的质数因子是自身的数字。

-- | A lazy infinite list of primes.
primes :: [Integer]
primes = mapMaybe isPrime factors
  where
    -- |  A number is prime if it's only prime factor is the number itself.
    isPrime (n, [p]) | n == p  = Just p
    isPrime _                  = Nothing

这个技巧在于我们手动开始因子列表，并且为了确定一个数字的质因数列表，我们只需要小于它平方根的质数。让我们看一下当我们消耗一些因子列表并尝试计算3的因子列表时会发生什么。我们正在消耗质数列表，取2（可以从我们手动给出的内容计算）。我们发现它不能被3整除，而且它大于3的平方根，因此没有更多可能的3的因子。因此，3的因子列表是[3]。由此，我们可以计算出3是另一个质数。等等。
2
更优美的代码，使用2和奇数来除以这个数字。
factors' :: Integral t => t -> [t]
factors' n
  | n < 0 = factors' (-n)
  | n > 0 = if 1 == n
               then []
               else let fac = mfac n 2 in fac : factors' (n `div` fac)
  where mfac m x
          | rem m x == 0 = x
          | x * x > m    = m
          | otherwise    = mfac m (if odd x then x + 2 else x + 1)
let fac = mfac n 2 in fac : factors' (n `div` fac) 这种写法不够优化，总是从2开始，可以从之前的 fac 开始。 - Will Ness
1
这是我的版本。不像其他人那么简洁，但我认为它非常易读和易懂。
import Data.List

factor :: Int -> [Int]
factor n
  | n <= 1 = []
  | even n = 2 : factor(div n 2)
  | otherwise =
    let root = floor $ sqrt $ fromIntegral n
    in
      case find ((==) 0 . mod n) [3, 5.. root] of
        Nothing  -> [n]
        Just fac -> fac : factor(div n fac)
0

我相信这段代码足够丑陋，足以让真正的 Haskell 程序员流泪，但它在 GHCI 9.0.1 中可以提供每个质因数的计数的质因数。

import Data.List
factors n = [x | x <- [2..(n`div` 2)], mod n x == 0] ++ [n]
factormap n = fmap factors $ factors n
isPrime n = case factormap n of [a] -> True; _ -> False
primeList (x:xs) = filter (isPrime) (x:xs)
numPrimes n a = length $ (factors n) `intersect` (takeWhile ( <=n) $ iterate (a*) a)
primeFactors n = primeList $ factors n
result1 n = fmap (numPrimes n) (primeFactors n)
answer n =  ((primeFactors n),(result1 n))

示例： ghci> answer 504
([2,3,7],[3,2,1])

答案是一个质因数列表和第二个列表显示每个质因数在提交的数字中出现的次数。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接