我的Haskell解决方案对欧拉＃3是无效的 [英] My Haskell Solution to Euler #3 is Inefficient

问题描述

我试图解决Haskell中的Euler问题3，其中涉及找到一个数字的最大素数因子。我的代码运行很长时间，似乎挂起。什么导致我的代码如此低效？

  primes = sieve（2：[3,5 ..]）
其中sieve（x：xs）= x：[y | （primesUnder n）中的素数n =过滤器（\ x  - > mod nx == 0） 
 primesUnder z = reverse（takeWhile（< z）primes）
 solve3 = head（primefactors 600851475143）
  

解决方案

你的主要问题是你正在检查巨大的素数 - 一直到 600851475143 。你可以通过观察两件事情来改善事情：

1. 每当你找到一个素数时，你可以减少你看到的最大素数除去该因素。


2. 您只需查找素数，直到达到目标的平方根。如果您的素数比这更大，并且您知道没有更小的因素，您就完成了。

一起使用这两项改进，即使没有你使用的仅仅检查素数的可分性的细节，也会使程序快速运行：

  factor = go （2：[3,5 ..]）其中
去（p：ps）n 
 | p * p> n = [n] 
 | n'mod` p == 0 = p：go（p：ps）（n`div` p）
 |否则=去ps n 
 main =打印。最后。因子$ 600851475143 
  

在ghci中：

  *主>主
 6857 
（0.00秒，0字节）
  

你可以看到我们只需检查数量高达 6857 的数字 - 比您的方法要小8个数量级。

独立地，你的筛子很慢。您可以在wiki上查看有关如何快速查找素数的想法。

I am attempting to solve Euler problem 3 in Haskell, which involves finding the largest prime factor of a number. My code runs for a long time and seems to hang. What is causing my code to be so grossly inefficient?

primes = sieve (2:[3,5..])
 where sieve (x:xs) = x:[y | y <- (sieve xs), mod y x /= 0]
       sieve [] = []
primefactors n = filter (\x -> mod n x == 0) (primesUnder n)
 where primesUnder z = reverse (takeWhile (< z) primes)
solve3 = head (primefactors 600851475143)

解决方案

Your main problem is you're checking for enormous primes -- all the way up to 600851475143. You can improve things a lot by observing two things:

1. Every time you find a prime, you can decrease the maximum prime you look at by dividing away that factor.
2. You only have to look for primes until you reach the square root of the target. If your primes are bigger than that, and you know there are no smaller factors, you're done.

Using these two improvements together, even without the nicety that you used of only checking primes for divisibility, makes the program run in a snap:

factor = go (2:[3,5..]) where
    go (p:ps) n
        | p*p > n        = [n]
        | n `mod` p == 0 = p : go (p:ps) (n `div` p)
        | otherwise      = go ps n
main = print . last . factor $ 600851475143

In ghci:

*Main> main
6857
(0.00 secs, 0 bytes)

You can see that we only had to inspect numbers up to 6857 -- eight orders of magnitude smaller than what you would have to do with your approach.

Independently, your sieve is dog slow. You could have a look at the wiki for ideas about how to find primes quickly.

这篇关于我的Haskell解决方案对欧拉＃3是无效的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！