0


我知道..标题解释得不好..
如果您有更好的标题，请在评论中告诉我..
我正在制作一个素数生成器以供娱乐和学习..
这是我的代码：

divisors x xs = [ y | y <- [1]++xs++[x], x `mod` y == 0]
isPrime x xs = divisors x xs == [1,x]
primeLst = [ x | x <- [2..], isPrime x primeLst]

如您所见..我必须在生成新的素数时使用已经生成的素数以减少执行时间..
它不起作用..
有没有办法制作它？

4

3 回答 3

2

让我们从查看divisors函数开始。这是正确的，只有两个问题：

  1. xs争论应该是什么？从定义来看，它看起来应该是下面的所有素数x- 我们称它们为候选素数。所以如果x是10，那么候选素数应该是[2,3,5,7]。但是，这不是函数作为参数得到的。在您的代码中，xs是无限的素数列表。

  2. 从技术上讲，divisors不会返回所有除数。divisors 16 [2,3,5,7,11,13]例如，不会返回8。但这是一个小问题。

因此，如果我们可以divisors使用正确的素数列表进行调用，那么我们应该没问题，并且该isPrime函数也可以。

问题是获取候选素数列表。为了清楚起见，我先给出代码，然后解释：

primeLst = 2 : [ x | x <- [3..], isPrime x (takeWhile (\p -> p*p <= x) primeLst)]

我做了两个改变：

  1. 我通过将其粘贴在前面来确保primeLst包括。2

  2. 我通过从无限的素数列表中获取数字来限制候选素数，直到我达到一个高于我正在测试素数的数字的平方根的数字。在这样做时，我稍微改变了候选素数的定义，例如，候选素数26是[2,3,5]而不是[2,3,5,7,11,13,17,19,23]。但它仍然有效。

两个问题让你思考：

  1. 为什么它仍然适用于候选素数的新定义？

  2. 为什么以下代码行不起作用，即使它似乎应该给出候选素数的原始定义？

：

primeLst = 2 : [ x | x <- [3..], isPrime x (takeWhile (\p -> p < x) primeLst)]

最后一个问题很难，所以如果您有任何问题，请在评论中发表。

于 2013-05-22T21:12:51.643 回答
2 
dividedBy a b = a `mod` b == 0
isPrime x = null $ filter (x `dividedBy`) $ takeWhile (\y -> y * y <= x) primeLst
primeLst = 2:(filter isPrime [3..])

或者，更详细：

primeLst = 2:(filter isPrime [3..])
  where
    isPrime x = null $ primeDivisors x
    primeDivisors x = filter (x `dividedBy`) $ potentialDivisors x
    potentialDivisors x = takeWhile (\y -> y * y <= x) primeLst
    a `dividedBy` b = a `mod` b == 0
于 2013-05-22T21:13:25.410 回答
1

计算 的至少一个元素primeLst需要计算isPrime 2 primeLst需要计算 的至少两个元素divisors 2 primeLst需要计算 的至少两个元素[1]++primeLst++[2]需要计算 的至少一个元素primeLst。不会发生。

[1]++(primesLessThan x)++[x]您也许可以(primesLessThan x)使用primeLst.

于 2013-05-22T19:09:03.773 回答