haskell - Haskell 中的欧拉 26

问题描述

我正在尝试解决 Haskell 中 Project Euler 的问题#26，但我遇到了一些问题。

我已经设法弄清楚倒数的循环周期只与它的素数除数有关，所以我想我只需要找出循环周期最长的素数的倒数。于是我用 Haskell 写了一个算法：

isPrime :: Int -> Bool
isPrime k
    | k <= 1    = error "Seriously?"
    | otherwise = null [ x | x <- [2..floor(sqrt(fromIntegral k))], k `mod` x == 0]

lp = [x | x <- [7..1000], isPrime x]

s = map (\n -> head [x | x <- [ceiling(logBase 10 (fromIntegral n))..], 10^x `mod` n == 1]) lp

main::IO()
main = print $ maximum s

但是，它无法给出答案。我尝试使用 lamda，它可以产生循环周期的数字，带有几个素数，我设法得到正确的数字数（我希望算法不会有问题）。我还检查了 list 的输出s，它[6,2,6,16,18,45,23,15,3,5,63,没有结束。我不知道为什么会这样，因为如果我手动将函数应用于每个素数，我可以获得正确的输出。

谁能告诉我我的代码有什么问题，或者我的解决方法是错误的？谢谢。

标签： haskell

Int在这里不是一个好的选择，因为您使用10^x. Int是Bounded，所以绕过它的上限：

> maxBound :: Int
9223372036854775807

> (maxBound :: Int) + 1
-9223372036854775808

完全省略签名isPrime，我们得到

> :t lp
lp :: Integral b => [b]

试

> map (\n -> (n, head [x | x <- [ceiling(logBase 10 (fromIntegral n))..],
                           10^x `mod` n == 1])) 
      (lp :: [Int])
[(7,6),(11,2),(13,6),(17,16),(19,18),(23,45),(29,23),(31,15),(37,3),(41,5),(43,63),
 (47,Interrupted.

我们看到你的计算卡住了47。但是使用[Integer]（或什么都不用，所以它默认为Integer自己），我们成功地得到了完整的结果。你只是误解了它。重新阅读问题陈述，你会明白的。

_{（另外，上面代码片段中 43 的答案是不正确的，而 7、11、13 的答案是正确的。对于更大的数字得到错误的结果是一个强烈的信号，表明我们有一些整数环绕算术错误正在发生；那就是我是怎么发现的）。}

haskell - Haskell 中的欧拉 26

问题描述

解决方案

推荐阅读