vba - Sundaram 筛子

Question

我需要有人带我穿过 Sundaram 的筛子（维基）。假设我在数组中有一个整数列表(41,43,47,49,51,53,59) 。

现在上面提到的维基百科解释提到：*

当且仅当它的形式为 2(i+j+2ij)+1 时，奇数才会从最终列表中排除

*。我试图了解如何在程序中实现这一点（最好是 VBA）。这样输出将是(41,43,47,53,59)。

解释由衷感谢。

问候，

Answer 1

我在我的博客上讨论了 Sundaram 的筛子。该算法由以下伪代码给出：

function sundaram(n)
    m := n // 2
    sieve := makeArray(m+1, True)
    for i from 1 to m // 4
        for j from i to (m-i) // (2*i+1)
            sieve[i+j+2*i*j] := False
    ps := [2]
    for i from 1 to m
        if sieve[i]
            append 2*i+1 to ps
    return ps

Answer 2

根据 WP 文章，从 range 中删除一些数字后k=1...n，我们得到的结果为m=2k+1。这意味着所有ms 都是奇数。

现在，一个奇数复合必须是两个奇数的乘积：（2k+1 = (2i+1)(2j+1) = 4ij+2i+2j+1如果其中一个是偶数，则乘积也是偶数）。但这意味着k = 2ij + i + j。因此，筛子的操作。

正如这里很好解释的那样。