递归函数的空列表

为了好玩，我试着在Project Euler上做一些工作，但是现在我被困在一个问题上，想要继续前进，但似乎无法让我的函数工作。我试图计算给定整数的主因子。该功能适用于更小的数字，如13195：递归函数的空列表

> primeFactor 13195 
[29,13,7,5]

但是当我运行一个较大的数字，如600851475143：

> primeFactor 601851475143 
[]

这似乎很奇怪我。我知道Haskell是一个懒惰的语言，但我不认为它应该是偷懒......

primeFactor' :: Int -> [Int] 
primeFactor' n = [ p | p <- primes' [] [2 .. n], n `mod` p == 0 ] 
    where primes' :: [Int] -> [Int] -> [Int] 
     primes' ys [] = ys 
     primes' ys (x:xs) | x `notMultipleOf` ys = primes' (x:ys) xs 
          | otherwise   = primes' ys xs                       

-- helper function to primeFactor' 
notMultipleOf :: Int -> [Int] -> Bool 
notMultipleOf n [] = True 
notMultipleOf n xs = and [n `mod` x /= 0 | x <- xs]

来源

2013-12-20 patriques

Int有32位你不能存储数量（使用Integer）。

在另一方面，你可以使用Data.Numbers.Primes（和see code）：

> primeFactors 601851475143 
[3,3,23,1009,2881561] 
> primeFactors 600851475143 
[71,839,1471,6857]

来源

2013-12-20 10:16:04 josejuan

这是一个整数溢出错误。该Int类型只能代表人数达到2^31 - 1

>> maxBound :: Int 
2147483647

数您输入溢出 -

>> 601851465143 :: Int 
556043703

在另一方面，如果使用Integer类型没有溢出 -

>> 601851465143 :: Integer 
601851465143

来源

2013-12-20 10:22:43

老实说，我不知道你为什么得到一个空列表....或者任何东西。

您正在使用蛮力法来查找素数列表，并将所有数字除以所有更小的素数。这个尺度就像n^2一样。

这需要多长时间才能完成？

N^2 ~= (601851475143)^2 ~= 10^22 operations

这是一个有点比这更好的，因为素数的密度下降，但数量不多....我们剃掉的10^2倍考虑到这一点。在现代8核心4GHz机器上（假设每个操作1cpu周期....方式乐观），这应该采取

10^20 operations/(10^10 operation/sec) = 10^10 sec ~= 300 years

来完成。

您可能想要寻找一种新算法。

来源

2013-12-20 10:40:20 jamshidh

递归函数的空列表

回答

相关问题