1

我正在尝试 Euler Q3 项目，需要获得一个数字的最大素数。到目前为止，我已经获得了一对函数来返回给定数字的所有因子的列表，但这似乎是一种非常糟糕的方法（部分原因是我只需要最大的）。

get_factors :: (Integral a) => a -> [a] -> [a]
get_factors _ [] = []
get_factors t (x:xs)
    | t `mod` x == 0 = x:get_factors t xs
    | otherwise = get_factors t xs

factors :: (Integral a) => a -> [a]
factors x = get_factors x [x,x-1..1]

> factors 1000
> [1000,500,250,200,125,100,50,40,25,20,10,8,5,4,2,1]

如果你要启动递归函数，我需要一个“启动”函数，这对我来说似乎很奇怪（或者有一个函数，我必须两次传递相同的值，再次，对我来说似乎很愚蠢）。

你能指出我应该如何做这件事的正确方向吗？

4

3 回答 3

8

您应该尝试认识到您在这里所做的事情，即从列表中选择满足某些条件的元素，是一种非常常见的模式。该模式由filterPrelude 中的函数实现。

使用filter，您可以将函数编写为：

factors n = filter (\d -> n `mod` d == 0) [n, n-1 .. 1]

或者，等效地，您可以使用列表推导：

factors n = [d | d <- [n, n-1 .. 1], n `mod` d == 0]
于 2013-05-05T17:30:15.307 回答
4

Using a "launch" function for calling a recursive function is very common in Haskell, so don't be afraid of that. Most often it'd be written as

f = g someArgument
  where
    g = ...

in your case

factors :: (Integral a) => a -> [a]
factors x = get_factors [x,x-1..1]
  where
    get_factors [] = []
    get_factors (y:ys)
        | x `mod` y == 0   = y : get_factors ys
        | otherwise        = get_factors ys

This signals readers of your code that get_factors is used only here and nowhere else, and helps you to keep the code clean. Also get_factors has access to x, which simplifies the design.

Some other ideas:

  • It's inefficient to try dividing by all numbers. In problems like that it's much better to pre-compute the list of primes and factor using the list. There are many methods how to compute such a list, but for educational purposes I'd suggest you to write your own (this will come in handy for other Project Euler problems). Then you could take the list of primes, take a part of primes less or equal than x and try dividing by them.
  • When searching just for the largest factor, you have to search through all primes between 1 and x. But if x is composite, one of its factors must be <= sqrt(n). You can use this to construct a significantly better algorithm.
于 2013-05-05T17:32:51.217 回答
2

我认为遍历 [n, n-1..] 这样的每个数字不是一个好主意，因为问题是 600851475143。

largest_factors :: Integer -> Integer
largest_factors n = helper n 2
    where
        helper m p  
            | m < p^2 = m
            | m == p = m
            | m `mod` p == 0 = helper (m `div` p) p
            | otherwise = helper m (p+1)

我所做的是，一旦它发现某个数字，比如说 p，除以数字 n，它就除以它。这个在我的电脑上工作得很好。这在一秒钟内给了我解决方案。

于 2013-05-05T20:24:18.637 回答