解决此问题的Haskell方法是什么？

Haskell的新手。我有以下代码解决此问题的Haskell方法是什么？

fac :: Integer -> [Integer] 
fac x = take 1 $ map (x `mod`) $ reverse [2 .. xs] 
    where xs = floor $ sqrt $ fromIntegral x

我想显示从[2 .. xs]使得x mod y == 0第一个值。但是我不能使用filter，因为只能从mod输出。我该怎么做呢？如果你想在这里reverse，或究竟是你的目标

fac x = take 1 $ filter ((== 0).(x `mod`)) $ reverse [2 .. xs] 
    where xs = floor $ sqrt $ fromIntegral x

不确定：

来源

2014-05-06 Chris

你可以使用filter。只需编写(==0)和(x `mod`)作为filter的第一个参数。

如果你正在尝试做欧拉问题3，这将是一个非常痛苦的解决方法。

我建议如下：

定义函数，你有where子句中的东西，即isqrt = round . sqrt . fromIntegral
定义两个函数isPrime和primeList是相互递归计算素数您应该在isPrime的定义中使用isqrt，但实际上并不需要使用isqrt;我觉得写这个函数比较容易。（有一个提示下文，了解如何做到这一步）
使用primeList，定义一个递归factorize功能输出从问题和返回素数的列表（或类似的东西）
比化数在列表中

最大的黄金上面我所建议的通常不是快速计算非常大的质数很大，但它应该是足够了这一问题。本文将进入更详细的原因：http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

对于未来的数论与PE的问题，考虑使用这个库：https://hackage.haskell.org/package/arithmoi-0.2.0.4

其他评论：

相反的take 1，你其实应该使用head;它稍好一些。

此外，由于您将在此处处理的最大号码是600851475143，因此您实际上不需要具有类型Integer -> [Integer]的功能。 32位Int没有办法，因为maxBound :: Int是2147483647.然而，maxBound :: Int64是9223372036854775807，这比你需要的多得多。因此，您可以将函数定义为Int64 -> [Int64]（如果机器已经是64位，则只需要Int -> [Int]）。

提示：

primeList应该被定义为像primeList = 2 : 3 : filter isPrime [5,7..]，但你可以决定要作为要与此）花哨;再次，这些定义应该是相互递归的。

来源

2014-05-06 14:30:46 Emil

我不太清楚你的意思是通过相互递归。我得到isPrime会驱动primeList。但为什么primeList反馈到isPrime？ – Chris

如果某些'm'除以'n'，'n'不是素数。但是，如果'm'除了'n'，那么'm'的任何除数也会将'n'分开。所以，为了确定'n'是否是素数，你只需要知道它是否可以被某个素数整除。原来你只需要用小于或等于'sqrt（n）'的素数对它进行修改（如果你以前没有见过这个，试着向自己证明这个结果是真的）。如果任何余数等于零，那么'n'不是素数。 – Emil

另外，我说'primeList'应该是上面答案中的一个函数，但事实并非如此。 'primeList'只是一个列表，你可能已经想通了。 – Emil

fac x = take 1 $ filter (\y -> x `mod` y == 0) $ reverse [2 .. xs] 
    where xs = floor $ sqrt $ fromIntegral x

，或者是点免费。

来源

2014-05-06 01:45:39

我想显示从所述第一值[2 .. XS]使得x mod y操作== 0

在这种情况下，则不应使用reverse：

fac x = take 1 $ filter (\y -> x `mod` y == 0) $ reverse [2 .. xs] 
    where xs = floor $ sqrt $ fromIntegral x

如果要查找从xs开始的第一个值，例如mod x y == 0，则也不需要使用reverse：

fac x = take 1 $ filter (\y -> x `mod` y == 0) $ [xs, xs-1 .. 2] 
    where xs = floor $ sqrt $ fromIntegral x

来源

2014-05-06 01:54:44

只是为了给出更多的上下文，我正在研究项目欧拉的问题3：什么是数字600851475143的最大素因子？我正在考虑使用基于此的递归来获得答案。想知道是否有更好的方法来处理这个问题。 – Chris

您可以使用过滤器。这里有一个单行（如果你算进口的话，还有两行）：

import Data.Ix (range) 
fac x = head . filter ((==) 0 . mod x) . curry range 2 . floor . sqrt . fromIntegral $ x

来源

2014-05-06 12:09:30 Bolo

解决此问题的Haskell方法是什么？

回答

相关问题