1

我认为这在技术上是车轮分解。我正在尝试重新压缩我的程序对 Eratosthenes 筛的表示，它只包含可能是素数的数字索引。

一些背景：

最基本的轮子是[2]：跟踪2作为第一个素数，筛子只包含奇数索引。(50%))

下一个轮子是[2 3]：跟踪2和3作为第一个素数，筛子只包含2*3=6之间的间隙（即1和5）。索引的形式为 6k+1 和 6k+5。(33%)

下一个轮子是 [2 3 5]：跟踪 2、3 和 5 作为第一个素数，筛子只需要 8 位来表示大小为 30 的区间。（27%）

清除数字倍数的位时，我使用此循环找到这些倍数：

def multiplesIndices (self, i):
    for gap in self.gaps[1:]:
        ret = i * (self.product * 0 + gap)
        if ret > len (self): break
            yield ret
    for k in xrange (1, len (self) / i / self.product + 1):
        for gap in self.gaps:
            ret = i * (self.product * k + gap)
            if ret > len (self): break
            yield ret

问题在于设置车轮所涉及的时间，以及压缩比的收益递减。好吧，那和 rn 更改为不同的车轮尺寸需要大量的重新计算。此外，通过改变轮子尺寸，我认为我可以影响渐近复杂度。

所以我提出的解决方案是使用小轮子来初始化更大的轮子：[2 3] (6/2) 获得 [2 3 5] (30/8) 轮子中的间隙 [2 3 5] 获得间隙[2 3 5 7] (210/48) 轮

我需要帮助的地方是将已经计算的小筛子映射到要计算的大筛子，这样我就可以避免重新筛选从 1 开始的所有内容。获取前 30 个素数，使用它们找到接下来的 210-30 个素数，用它们来找到接下来的 480-210 个素数。

更具体地说，我需要帮助反转此函数（或正确实现 invIndexOf()）：

def indexOf (self, n):
    if not self.isValidIndex (n): raise Exception ()
    ret = n / self.product * len (self.gaps) + self.gaps.index (n % self.product)
    assert n in self.invIndexOf (ret)
    return ret

此外，自从我计算出任何事物的渐近复杂性以来已经有几年了。我很确定这是一种改进，尽管不是很大。

4

0 回答 0