python - 在python中使Eratosthenes筛分更有效的内存？

Question

Eratosthenes 内存约束问题的筛选
我目前正在尝试为 Kattis 问题实现一个版本的埃拉托色尼筛，但是，我遇到了一些我的实现无法通过的内存限制。
这是问题的链接statement .简而言之，问题要我首先返回小于或等于 n 的素数的数量，然后解决一定数量的查询，如果数字 i 是素数与否。有 50 MB 内存使用限制以及仅使用 python 的标准库(没有 numpy 等)。内存限制是我卡住的地方。
到目前为止，这是我的代码:

import sys

def sieve_of_eratosthenes(xs, n):
    count = len(xs) + 1
    p = 3 # start at three
    index = 0
    while p*p < n:
        for i in range(index + p, len(xs), p):
            if xs[i]:
                xs[i] = 0
                count -= 1

        temp_index = index
        for i in range(index + 1, len(xs)):
            if xs[i]:
                p = xs[i]
                temp_index += 1
                break
            temp_index += 1
        index = temp_index

    return count


def isPrime(xs, a):
    if a == 1:
        return False
    if a == 2:
        return True
    if not (a & 1):
        return False
    return bool(xs[(a >> 1) - 1])

def main():
    n, q = map(int, sys.stdin.readline().split(' '))
    odds = [num for num in range(2, n+1) if (num & 1)]
    print(sieve_of_eratosthenes(odds, n))

    for _ in range(q):
        query = int(input())
        if isPrime(odds, query):
            print('1')
        else:
            print('0')


if __name__ == "__main__":
    main()

到目前为止，我已经做了一些改进，比如只保留所有奇数的列表，这将内存使用量减半。我也确定代码在计算素数时按预期工作(没有得到错误的答案)。我现在的问题是，我怎样才能使我的代码更有效地使用内存？我应该使用其他一些数据结构吗？用 bool 值替换我的整数列表？位阵列？
非常感谢任何建议!
编辑
在对 python 中的代码进行一些调整后，我遇到了一个问题，我的分段筛的实现无法满足内存要求。
相反，我选择用 Java 实现该解决方案，这花费了很少的精力。这是代码:

  public int sieveOfEratosthenes(int n){
    sieve = new BitSet((n+1) / 2);
    int count = (n + 1) / 2;

    for (int i=3; i*i <= n; i += 2){
      if (isComposite(i)) {
        continue;
      }

      // Increment by two, skipping all even numbers
      for (int c = i * i; c <= n; c += 2 * i){
        if(!isComposite(c)){
          setComposite(c);
          count--;
        }
      }
    }

    return count;

  }

  public boolean isComposite(int k) {
    return sieve.get((k - 3) / 2); // Since we don't keep track of even numbers
  }

  public void setComposite(int k) {
    sieve.set((k - 3) / 2); // Since we don't keep track of even numbers
  }

  public boolean isPrime(int a) {
    if (a < 3)
      return a > 1;

    if (a == 2)
      return true;

    if ((a & 1) == 1)
      return !isComposite(a);
    else
      return false;

  }

  public void run() throws Exception{
    BufferedReader scan = new BufferedReader(new InputStreamReader(System.in));
    String[] line = scan.readLine().split(" ");

    int n = Integer.parseInt(line[0]); int q = Integer.parseInt(line[1]);
    System.out.println(sieveOfEratosthenes(n));

    for (int i=0; i < q; i++){
      line = scan.readLine().split(" ");
      System.out.println( isPrime(Integer.parseInt(line[0])) ? '1' : '0');
    }
  }

我个人还没有找到在 Python 中实现这个 BitSet 解决方案的方法(仅使用标准库)。
如果有人在 python 中使用分段筛、位数组或其他东西偶然发现了对这个问题的巧妙实现，我会很想看看解决方案。

Answer 1

我学到了一个技巧just yesterday - 如果将数字分成 6 个一组，则 6 个中只有 2 个可能是质数。其他的可以被 2 或 3 整除。这意味着跟踪 6 个数字的素数只需要 2 位；一个包含 8 位的字节可以跟踪 24 个数字的素数!这大大减少了筛子的内存需求。
在 Windows 10 上的 Python 3.7.5 64 位中，以下代码没有超过 36.4 MB。

remainder_bit = [0, 0x01, 0, 0, 0, 0x02,
                 0, 0x04, 0, 0, 0, 0x08,
                 0, 0x10, 0, 0, 0, 0x20,
                 0, 0x40, 0, 0, 0, 0x80]

def is_prime(xs, a):
    if a <= 3:
        return a > 1
    index, rem = divmod(a, 24)
    bit = remainder_bit[rem]
    if not bit:
        return False
    return not (xs[index] & bit)

def sieve_of_eratosthenes(xs, n):
    count = (n // 3) + 1 # subtract out 1 and 4, add 2 3 and 5
    p = 5
    while p*p <= n:
        if is_prime(xs, p):
            for i in range(5 * p, n + 1, p):
                index, rem = divmod(i, 24)
                bit = remainder_bit[rem]
                if bit and not (xs[index] & bit):
                    xs[index] |= bit
                    count -= 1
        p += 2
        if is_prime(xs, p):
            for i in range(5 * p, n + 1, p):
                index, rem = divmod(i, 24)
                bit = remainder_bit[rem]
                if bit and not (xs[index] & bit):
                    xs[index] |= bit
                    count -= 1
        p += 4

    return count


def init_sieve(n):
    return bytearray((n + 23) // 24)

n = 100000000
xs = init_sieve(n)
sieve_of_eratosthenes(xs, n)
5761455
sum(is_prime(xs, i) for i in range(n+1))
5761455

编辑:了解其工作原理的关键是筛子会产生重复模式。对于素数 2 和 3，模式每 2*3 或 6 个数字重复一次，而在这 6 个数字中，4 个已经不可能成为素数，只剩下 2 个。没有什么可以限制您选择素数来生成模式，除了也许是因为 yield 递减规律。我决定尝试在混合中添加 5，使模式每 2*3*5=30 个数字重复一次。在这 30 个数字中，只有 8 个可以是质数，这意味着每个字节可以跟踪 30 个数字而不是上面的 24 个!这为您提供了 20% 的内存使用优势。
这是更新后的代码。我还稍微简化了它，并随着它的进行去掉了素数的计数。

remainder_bit30 = [0,    0x01, 0,    0,    0,    0,    0, 0x02, 0,    0,
                   0,    0x04, 0,    0x08, 0,    0,    0, 0x10, 0,    0x20,
                   0,    0,    0,    0x40, 0,    0,    0, 0,    0,    0x80]

def is_prime(xs, a):
    if a <= 5:
        return (a > 1) and (a != 4)
    index, rem = divmod(a, 30)
    bit = remainder_bit30[rem]
    return (bit != 0) and not (xs[index] & bit)

def sieve_of_eratosthenes(xs):
    n = 30 * len(xs) - 1
    p = 0
    while p*p < n:
        for offset in (1, 7, 11, 13, 17, 19, 23, 29):
            p += offset
            if is_prime(xs, p):
                for i in range(p * p, n + 1, p):
                    index, rem = divmod(i, 30)
                    if index < len(xs):
                        bit = remainder_bit30[rem]
                        xs[index] |= bit
            p -= offset
        p += 30

def init_sieve(n):
    b = bytearray((n + 30) // 30)
    return b