Haskell中的主要因素 [英] Prime factors in Haskell

问题描述

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

现在我只知道如何生成素数：

pre $ primes = map head $ iterate（\（x： xs） - > [y | y <-xs，y`mod` x / = 0]）[2 ..]


确定 n 的主要因素的简单方法是> >

• 在 [2..n-1]中搜索第一个除数 d code $
• 否则返回 n （因为 n 是素数）



代码：

  prime_factors :: Int  - > [Int] 
 
 prime_factors 1 = [] 
 prime_factors n 
 |因素== [] = [n] 
 |否则=因素++ prime_factors（n`div`（头部因子））
其中factor =取1 $ filter（\ x  - >（n`mod` x）== 0）[2 .. n -1] 
  

这显然可以使用很多优化（仅从2到sqrt（N） ，缓存到目前为止发现的素数，并计算除此之外的分数。）

更新

一个使用大小写的稍微修改的版本（如@ user5402所示）：

  prime_factors n = 
案例因素
 []  - > [n] 
 _  - >因子++ prime_factors（n`div`（head factor））
其中factor =取1 $ filter（\ x  - >（n`mod` x）== 0）[2 .. n-1 ] 
  

I'm new in Haskell.

How to generate list of lists which contains prime factors of next integers?

Now I only know how to generate prime numbers:

primes = map head $ iterate (\(x:xs) -> [y | y<-xs, y `mod` x /= 0 ]) [2..]

解决方案

A simple approach to determine the prime factors of n is to

• search for the first divisor d in [2..n-1]
• if D exists: return d : primeFactors(div n d)
• otherwise return n (since n is prime)

Code:

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]

This obviously could use a lot of optimization (search only from 2 to sqrt(N), cache the prime numbers found so far and compute the division only for these etc.)

UPDATE

A slightly modified version using case (as suggested by @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]

这篇关于Haskell中的主要因素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！