haskell - Sundaram 筛 - 列表理解

Question

我正在尝试编写一个函数，使用 "Sieve of Sundaram" algorithm 从 1..n 计算所有奇数素数.

这是我的尝试:

sSund :: Integer -> [Integer]
sSund n = [ i * 2 + 1 | i <- [1..n], j <- [f i], (i + j + 2 * i * j) > n ] 
  where f 1 = 1 
        f y = y + 1 --use function f because i don't know how insert 1 into j's list

但它给出了一些错误的数字，如 9、15、21、25 等。

*Main> sSund 30
[7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49,51,53,55,57,59,61]

我究竟做错了什么？

Answer 1

这个怎么运作

Sundaram 的 seive 专注于奇数 2n+1，排除那些是数字的乘积。

如果两个数相乘得到一个奇数，它们一定都是奇数，所以我们的数 2n+1 = (2i+1)(2j+1)。如果我们将其相乘，我们得到 2n+1 = 4ij + 2i +2j + 1，我们可以将其简化为 2n=4ij+2i+2j，它再次简化为 n=2ij+i+j。所以如果我们可以把它写成 2ij+i+j，我们就不想要 n。这对于任何数字 i 和 j 都是正确的，但是只需去掉 i<=j 的数字就可以了，因为否则你肯定会两次排除同一个数字。

修复你的代码

在您的代码中，您生成了一些数字 i + j + 2 * i * j被排除，但实际上您只是排除了 i而不是 i + j + 2 * i * j . j<-[f i]只给你一个j列表中的值，而不是 i 中的所有数字高达 n , 你应该写成 [i..n] .

首先生成排除列表要简单得多:

sSundDelete :: Integer -> [Integer]            
sSundDelete n = [i+j+2*i*j|i<-[1..n], j<-[i..n]]

在这里，我决定只允许 i和 j介于 1 之间和 n , 因为否则 2ij+i+j 肯定大于 n。

现在我们可以制作一个数字列表 x不包括这些数字，然后用公式 2*n+1 将它们设为奇数:

sSund :: Integer -> [Integer]
sSund n = let del = sSundDelete n in
     2:[2*x+1 | x <- [1..n], not (x `elem` del)]

哪个正确地给了你

> sSund 30
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61]

加快速度

不过，它并没有想象的那么快，因为如果你看

> sSundDelete 10
[4,7,10,13,16,19,22,25,28,31,12,17,22,27,32,37,42,47,52,24,31,38,45,52,59,66,73,40,49,58,67,76,85,94,60,71,82,93,104,115,84,97,110,123,136,112,127,142,157,144,161,178,180,199,220]

它的数字比我们需要的大得多 - sSund 10仅达到 2*10+1=21。这意味着我们会一次又一次地检查我们的数字与我们没有考虑过的数字!

最简单的方法是重写 sSundDelete说

sSundDelete n = [i+j+2*i*j|i<-[1..n], j<-[i..n],i+j+2*i*j<=n]

非常像你所做的，或者

sSundDelete n = filter (<= n) [i+j+2*i*j|i<-[1..n], j<-[i..n]]

使用一些数学来加快速度

这些的问题是它们产生了太多的数字然后把它们扔掉。只生成我们需要的数字会更快。

实际上，我认为最好计算一下要走多远。最小的 j我们将永远使用的是 i , 所以 2ij+i+j 的最小值可以是 2i2+2i。如果我们不希望它超过 n，我们需要 2i2+2i<=n，我们可以将其重写为 2i(i+1)<=n。正确性比效率更重要，所以稍微超过 n 是可以的，但重要的是不要错过 n 以下的数字，所以我们可以说 2i2<=n。这可以表示为 i <= floor (sqrt (fromIntegral n / 2)) ( floor 截断小数，所以 floor 35.7 是 35， fromIntegral 在这里用于将 n 转换为浮点数(允许非整数)，因此我们可以进行除法和平方根。

这需要大量的工作，但现在我们可以计算一次有多大 i应该去:

sSundDelete n = filter (<= n) [i+j+2*i*j|i<-[1..floor (sqrt (fromIntegral n / 2))], j<-[i..n]]

我们可以在 j 上做类似的工作。我们想要 2ij+i+j<=n，我们可以将其重新排列为 (2i+1)j<=n-i，这可以作为 j<=floor( (n'-i')/(2*i'+1))在哪里 i'=fromIntegral i和 n'=fromIntegral n .这给了我们

sSundDelete n = [i+j+2*i*j|let n'=fromIntegral n,
                           i<-[1..floor (sqrt (n' / 2))],
                           let i' = fromIntegral i,
                           j<-[i..floor( (n'-i')/(2*i'+1))]]

这让我不会放弃等待 sSund 5000计算第二个素数!