java - 如何在Java中从内存中逐位读取/写入

Question

从问题得出问题:找到所有 < 10^9 的素数。我用“埃拉托斯特尼筛法”来解决，我尝试用一​​位来表示每个数字的状态。所以，以下是我的代码

// n is the input integer
byte[] allNum = new byte[n/8 + 1];
ArrayList<Integer> result = new ArrayList<Integer>();
for (int i = 2; i < n; i++) {
    if ((allNum[i/8]>>(i%8) & 0x1) == 0) {
        result.add(i);
        for (int j = 2; i*j < n; j++) {
            allNum[i*j/8] |= 1 << i*j%8; 
        }
    }
}
return result;

是否有更好的数据结构用于此目的？非常感谢。

Answer 1

您可以使用 BitSet:

BitSet composites = new BitSet(n + 1);
for (int i = 2; i <= n; ++i) 
  if (!composites.get(i)) {
    ... /* It's prime. */
    for (int multiple = 2*i; multiple > 0 && multiple <= n; multiple+=i) 
      composites.set(multiple); /* Strike out every i-th number. */
  }