3

这是对 Project Euler 任务 #3 的剧透！如果您想自己解决，请不要继续阅读。

我正在尝试通过为 Project Euler 编写程序来学习 Haskell。目前我正在尝试解决任务＃3，它要求数字 600851475143 的最大素数。

为此，我创建了一个liste包含所有数字的列表，这些数字是这个数字的除数（直到它的平方根）。我现在的策略是，计算这些数字的除数，决定它们是否是素数。

number = 600851475143
-- sn = sqrt number
sn = 775146

liste = [x | x <- [1..sn],  (mod number x == 0)]
-- liste = [1,71,839,1471,6857,59569,104441,486847]

primelist :: Int -> [Int]
primelist z = [y | y <- [1..z], mod z y == 0] 

main = print [primelist x | x <- liste]

结果应该出现在这里，应该是一个包含 8 个列表的列表，其中包含 的元素的除数liste。相反，列表

[[1],[1,3],[1,29],[1,3,29,87]]

被打印。

如何解释这种行为？

4

2 回答 2

6

问题是类型声明primelist :: Int -> [Int]。它强制 Haskell 使用本机整数，即 32 位平台上的 32 位整数。然而，如果你忽略它，Haskell 会推断函数类型为Integer -> [Integer]. 整数允许以任意精度进行计算，但比本机类型慢一点。

引用Haskell FAQ 中的“Integer 和 Int 有什么区别” ：

Int 上的操作可以比 Integer 上的操作快得多，但是溢出和下溢会导致奇怪的错误。

现在这不是事实。

于 2013-06-01T22:24:18.993 回答
0

我不确定这是否会对您有所帮助，但我也正在通过 Project Euler 来帮助自学 Haskell，我设计了以下解决方案：

defacto :: Integer -> Integer -> Integer
defacto x p | x == p = 1
            | x`mod`p==0 = defacto (x`div`p) p
            | otherwise = x

gpf :: Integer -> Integer
gpf = \x -> prim (x,primes)

prim :: (Integer,[Integer]) -> Integer
prim (x,(p:ps)) | p > x = 1
                | (defacto x p) == 1 = p
                | otherwise = prim((defacto x p),ps)

n :: Integer
n = 600851475143

在这里，defacto从一个数中分解一个素数，因此defacto 2 12返回 4 并defacto 5 14返回 14。gpf是一个查找最大素数因子的函数，尽管它需要一个素数列表x才能在范围内。关键组件是prim，如果数字小于下一个素数，则返回 1；如果 x 是该素数的完美幂（即，如果所有其他小于 p 的素数都已被排除在外），则返回其素数列表中的第一个素数x)，否则对已分解的 x 和截断的素数列表执行递归调用。这具有在线性遍历素数列表的同时不断缩小 x 的效果，因此我们不需要测试任何不能分解为 x 的素数，并且我们不需要在 x 的缩减值上继续重新测试相同的素数。希望这对您有所帮助。

于 2014-05-13T22:48:29.370 回答