我是 Haskell 新手。
如何生成包含下一个整数的质因数的列表列表？
目前，我只知道如何生成素数：
primes = map head $ iterate (\(x:xs) -> [y | y<-xs, y `mod` x /= 0 ]) [2..]
确定
nd中搜索第一个除数
[2..n-1]d : primeFactors(div n d)nn代码：
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)，缓存到目前为止找到的质数并仅计算这些除法等）
更新
稍微修改的版本使用案例（如@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]
直到分红
mnmnn实际使用的所有除数列表是原始
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)
primesprimes = 2 : filter (\n-> head (factors n) == n) [3,5..]
这是一个性能良好且易于理解的实现，其中
isPrimeprimesprimesprimeFactorsprimes(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]
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]我刚刚解决了这个问题。这是我的解决方案。
两个帮助功能是
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)]
更优雅的代码，使用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)
这是我的版本。不像其他的那么简洁，但我认为它非常可读且易于理解。
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)
我确信这段代码丑陋得足以让真正的 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> 答案 504
([2,3,7],[3,2,1])
答案是质因数列表和显示每个质因数的第二个列表 质因数在提交的数字中。
这段代码怎么样？我担心我会进行不必要的评估，以便在前两个之后达到
6*m+56*m+7primeFactors :: Integer -> [Integer]
primeFactors n | n <= 1 = []
| otherwise = k : primeFactors (n `div` k)
where
k | n `mod` 2 == 0 = 2
| n `mod` 3 == 0 = 3
| otherwise = go 0
where
go m | n `mod` (6*m+5) == 0 = 6*m+5
| n `mod` (6*m+7) == 0 = 6*m+7
| otherwise = go (m+1)
为什么要采用这种形式？您可以使用第一个，
2*n6*n+36*n+56*n+7