3

我是 Haskell 的新手，正在修补欧拉项目的问题。我对问题 #3 的解决方案太慢了。起初我试过这个：

-- Problem 3
-- The prime factors of 13195 are 5, 7, 13 and 29.
-- What is the largest prime factor of the number 600851475143 ?

problem3 = max [ x | x <- [1..n], (mod n x) == 0, n /= x]
    where n = 600851475143

然后我将其更改为全部返回x，而不仅仅是最大的一个。

problem3 = [ x | x <- [1..n], (mod n x) == 0, n /= x]
        where n = 600851475143

30 分钟后，列表仍在处理中，输出如下所示

[1,71,839,1471,6857,59569,104441,486847,1234169,5753023,10086647,87625999,408464633,716151937

为什么这么慢？我是在做一些非常错误的事情还是这种任务是正常的？

4

5 回答 5

10

使用您的解决方案，大约有 6000 亿个可能的数字。正如 delnan 所指出的，让每个数字的检查速度更快并不会产生太大的影响，我们必须限制候选人的数量。

您的解决方案似乎也不正确。59569 = 71 * 839不是吗？这个问题只询问主要因素。请注意，71并且839在您的列表中，因此您正在做正确的事情。实际上，您正在尝试找出所有因素。

我认为最显着的效果是在继续之前将因素分开。

euler3 = go 2 600851475143
  where
    go cand num
      | cand == num           = [num]
      | cand `isFactorOf` num = cand : go cand       (num `div` cand)
      | otherwise             =        go (cand + 1) num

isFactorOf a b = b `mod` a == 0

这似乎是一个明显的优化，但它依赖于 if both aand bdivides cand ais coprime to bthen adivides的事实c/b。

如果你想做更多，这里已经提到了常见的“只检查直到平方根”的技巧。可以将相同的技巧应用于此问题，但不幸的是，在此实例中没有显示性能增益：

euler3 = go 2 600851475143
  where
    go cand num
      | cand*cand > num       = [num]
      | cand `isFactorOf` num = cand : go cand       (num `div` cand)
      | otherwise             =        go (cand + 1) num

isFactorOf a b = b `mod` a == 0

在这里，当候选数大于剩余数的平方根 ( num) 时，我们知道它num一定是素数，因此是原始数 ( 600851475143) 的素因数。

仅考虑素数就可以删除更多候选者，但这稍微高级一些，因为您需要采用合理的性能方式来生成素数。有关执行此操作的方法，请参阅此页面。

于 2013-07-30T12:13:24.687 回答
3

它做了很多工作！（它也会给你错误的答案，但这是一个单独的问题！）

有一些非常快速的方法可以通过先考虑问题来加快速度：

  • 您正在对所有数字应用您的函数1..n，并检查它们中的每一个以确保它不是n。相反，您可以查看所有数字1..n-1并跳过n不同的检查（尽管它们很小）。
  • 答案是奇数，因此您可以非常快速地过滤掉任何偶数，方法是使用 from1..(n-1)/2并检查2x而不是x。
  • 如果您考虑一下，所有因素都是成对出现的，因此您实际上可以从1..sqrt(n)（或者1..sqrt(n)/2如果您忽略偶数）搜索并在每个步骤中输出成对的数字。

与此函数的性能无关，但值得注意的是，您在这里实现的将找到一个数字的所有因数，而您想要的只是最大的质因数。所以要么你必须测试你的每个除数的素数（这又会很慢），或者你可以一步实现这两个。您可能想查看“筛子”，最简单的是 Eratosthenes 筛子，以及如何实现它们。

于 2013-07-30T11:30:57.583 回答
1

对于大数字，一个数字的完整分解可能需要很长时间。对于 Project Euler 问题，暴力解决方案（这就是）通常不足以在您的一生中找到答案。

提示：你不需要找到所有的质因数，只需要找到最大的一个。

于 2013-07-30T11:25:25.303 回答
0

TL; DR：你做的两件事不是最优的，是：不停留在平方根，不划分每个最小的因子，因为它们被发现了。

这是HaskellElephant 的答案中显示的（第二个）分解代码的一点推导。我们从您的代码开始：

f1 n = [ x | x <- [2..n], rem n x == 0]
n3 = 600851475143

Prelude> f1 n3
[71,839,1471,6857,59569,104441,486847Interrupted.

所以它不会在任何合理的时间内完成，并且它产生的一些数字不是素数......但是不是在列表理解中添加素数检查，让我们注意 71是素数。产生的第一个数f1 n是的最小除数，n因此它是素数。如果不是，我们会首先找到它的最小除数——矛盾。

所以，我们可以把它划分出来，继续寻找新约数的素因数：

f2 n = tail $ iterate (\(_,m)-> (\f->(f, quot m f)) . head $ f1 m) (1,n) 

Prelude> f2 n3
[(71,8462696833),(839,10086647),(1471,6857),(6857,1),(*** Exception: Prelude.hea
d: empty list

（错误，因为f1 1 == []）。我们完成了！（6857是答案，在这里......）。让我们总结一下：

takeUntil p xs = foldr (\x r -> if p x then [x] else x:r) [] xs
pfactors1 n = map fst . takeUntil ((==1).snd) . f2 $ n   -- prime factors of n

试用我们新推出的解决方案，

Prelude> map pfactors1 [n3..]
[[71,839,1471,6857],[2,2,2,3,3,1259Interrupted.

突然间，我们在没有小除数的数字上遇到了新的低效率墙。但是如果n = a*b和1 < a <= b，那么等 只测试一个数字的平方根，找到它的最小除数a*a <= a*b == n就足够了。

f12 n = [ x | x <- takeWhile ((<= n).(^2)) [2..n], rem n x == 0] ++ [n]
f22 n = tail $ iterate (\(_,m)-> (\f->(f, quot m f)) . head $ f12 m) (1,n) 
pfactors2 n = map fst . takeUntil ((==1).snd) . f22 $ n

半小时内无法完成的事情现在在一秒钟内完成（在典型的高性能机器上）：

Prelude> f12 n3
[71,839,1471,6857,59569,104441,486847,600851475143]

sqrt n3根本不需要上面的所有除数。我们无条件地将n自己添加为最后一个除数，f12因此它能够处理素数：

Prelude> f12 (n3+6)
[600851475149]

由于n3 / sqrt n3 = sqrt n3 ~= 775146，您最初的尝试f1 n3应该需要大约一周的时间才能完成。这就是优化在平方根处停止的重要性。

Prelude> f22 n3
[(71,8462696833),(839,10086647),(1471,6857),(6857,1),(1,1),(1,1),(1,1),(1,1),(1,
1),(1,1),(1,1),(1,1),(1,1),(1,1),(1,1),(1,1),(1,1),(1,1)Interrupted

我们显然已经将“Prelude.head：空列表”错误换成了非终止但富有成效的行为。

最后，我们将f22它们分成两部分并将它们分别融合到其他函数中，以简化代码。此外，我们不会再重新开始，就像一直从2f12中搜索最小除数一样：

-- smallest factor of n, starting from d. directly jump from sqrt n to n.
smf (d,n) = head $ [ (x, quot n x) | x <- takeWhile ((<=n).(^2)) [d..]
                                   , rem n x == 0] ++ [(n,1)]

pfactors n = map fst . takeUntil ((==1).snd) . tail . iterate smf $ (2,n)

这通过高阶函数表达了受保护的（共）递归，并且在功能上等同于上面提到的代码。以下现在运行顺利，我们甚至可以在那里找到一对孪生素数作为奖励： iterate

Prelude Saga> 地图 pfactors [n3..]
[[71,839,1471,6857],[2,2,2,3,3,1259,6628403],[5,120170295029],[2,13,37,227,27514
79],[3,7,7,11,163,2279657],[2,2,41,3663728507], [600851475149] ,[2,3,5,5,19,31,680
0809], [600851475151] ,[2,2,2,2,37553217197],[3,3,3,211,105468049],[2,7,11161,3845
351]，[5,67,881,2035853]，[2,2,3中断。
于 2013-07-30T23:28:13.423 回答
0

这是我对 Euler Project #3 的解决方案。在我的 Macbook Air 上只需 1.22 秒。

首先，我们应该找到给定数字的所有因子。但我们知道，偶数不能是素数（2 号除外）。因此，要解决 Euler Project #3，我们不需要全部，而只需要奇怪的因素：

    getOddFactors num = [ x | x <- [3,5..num], num `rem` x == 0 ]

但是我们可以优化这个功能。如果我们计划找到一个大于sqrt num的num因子，我们应该有另一个小于sqrt num的因子——这些可能的因子我们已经找到了。因此，我们可以通过sqrt num限制我们的可能因素列表：

    getOddFactors num = [ x | x <- [3, 5..(floor.sqrt.fromIntegral) num], 
                          num `rem` x == 0 ]

接下来我们想知道num的哪些奇因数是素数：

    isPrime number = [ x | x <- [3..(floor.sqrt.fromIntegral) number], 
                       number `rem` x == 0] == []

接下来我们可以使用函数isPrime过滤num的奇数因子以找到num的所有素数因子。但是为了使用 Haskell 的惰性来优化我们的解决方案，我们将函数filter isPrime应用于 num 的奇数因子的反向列表。一旦我们的函数找到第一个质数值，Haskell 就会停止计算并返回解：

    largestPrimeFactor = head . filter isPrime . reverse . getOddDivisors

因此，解决方案是：

    ghci> largestPrimeFactor 600851475143
    6857
    (1.22 secs, 110646064 bytes)
于 2014-07-08T13:33:37.300 回答