时间戳

首页 > 解决方案 > 第 n 个素数和素数因数

haskell - 第 n 个素数和素数因数

问题描述

通过 Haskell 教程，它说要编写一个函数“isPrime”来确定一个数字是否是素数。

我想出了：

isPrime :: Integer -> Bool
isPrime n = factors n == [1,n]
    where factors n = [x | x <- [1..n], n `mod` x == 0]

哪个有效。

但是我将如何询问第 n 个素数——例如，第 100 个素数是 541？

进一步研究质数，我发现了一个质数因子列表，如下所示：

primeFactors :: Integer -> [Integer]
primeFactors n = filter prime (factors n)
    where factors n = [x | x <- [1..n], n `mod` x == 0]
          prime n = factors n == [1,n]

这也有效。

然而，当你输入一个非常大的数字时，你会得到显着的延迟时间。

例如，它可以很好地执行以下操作：

ghci > primeFactors 419
[419]

ghci > primeFactors 5698
[2,7,11,37]                 -- did this one really fast...

ghci > primeFactors 76586
[2,149,257]                 -- and this one really fast... 

ghci > primeFactors 876350
[2,5,17,1031]               -- it hung up just a hair with this one...

ghci > primeFactors 4287635
[5,11,19,373]               -- hung up a little bit longer here...

ghci > primeFactors 34598274
[2,3,5766379]               -- hung up for quite a while here...

ghci > primeFactors 208346758
[2,104173379]               -- and for a very long time with this one!

该教程建议找到 62451532000 的主要因素，并且在大约 5 分钟后，我仍在等待。

是什么导致了滞后时间，加快速度的最佳方法是什么？

标签： haskell

解决方案

滞后时间是由于因素的作用。它从 迭代1到n。所以，如果n是62451532000，至少会有62451532000步骤。这步骤太多了。

有很多方法可以加快速度。实际上有这么多，一个人可以写一本书。我建议你查找分解。

现在，尝试实现这个简单的技巧。任何时候d都是 的一个因素n，所以也是n/d。如果你在下面寻找所有因素√n，并利用这个技巧，你就会找到所有因素。

这会将所需的步数从 减少62451532000到大约250000. 更易于管理。

推荐阅读