目前我有一个限制为 n < 2^32-1 的素数生成器。考虑到数组中元素的限制,我不确定如何进一步扩展限制。
筛选:
public class Main {
public static void main(String args[]){
long N = 2000000000;
// initially assume all integers are prime
boolean[] isPrime = new boolean[N + 1];
for (int i = 2; i <= N; i++) {
isPrime[i] = true;
}
// mark non-primes <= N using Sieve of Eratosthenes
for (int i = 2; i*i <= N; i++) {
// if i is prime, then mark multiples of i as nonprime
// suffices to consider mutiples i, i+1, ..., N/i
if (isPrime[i]) {
for (int j = i; i*j <= N; j++) {
isPrime[i*j] = false;
}
}
}
}
}
我如何修改它以超过 n = 2^32-1?
最佳答案
您可以使用 BitSet
的数组表示长位集的对象。这是完整的示例:
public class Main {
private static class LongBitSet {
// max value stored in single BitSet
private static final int BITSET_SIZE = 1 << 30;
BitSet[] bitsets;
public LongBitSet(long limit) {
bitsets = new BitSet[(int) (limit/BITSET_SIZE+1)];
// set all bits by default
for(int i=0; i<bitsets.length; i++) {
bitsets[i] = new BitSet();
int max = (int) (i == bitsets.length-1 ?
limit % BITSET_SIZE : BITSET_SIZE);
bitsets[i].set(0, max);
}
}
// clear specified bit
public void clear(long pos) {
bitsets[(int) (pos / BITSET_SIZE)].clear((int) (pos % BITSET_SIZE));
}
// get the value of the specified bit
public boolean get(long pos) {
return bitsets[(int) (pos / BITSET_SIZE)].get((int) (pos % BITSET_SIZE));
}
// get the number of set bits
public long cardinality() {
long cardinality = 0;
for(BitSet bs : bitsets) {
cardinality += bs.cardinality();
}
return cardinality;
}
}
public static void main(String args[]) {
long N = 4000000000L;
// initially assume all integers are prime
LongBitSet bs = new LongBitSet(N+1);
// clear 0 and 1: non-primes
bs.clear(0);
bs.clear(1);
// mark non-primes <= N using Sieve of Eratosthenes
for (long i = 2; i * i <= N; i++) {
if (bs.get(i)) {
for (long j = i; i * j <= N; j++) {
bs.clear(i * j);
}
}
}
System.out.println(bs.cardinality());
}
}
N = 4_000_000_000L
的程序占用大约 512Mb 的内存,运行几分钟并打印 189961812
,这是正确的素数低于 40 亿 according to Wolfram Alpha .如果你有足够的 RAM,你可以尝试设置更大的 N。
关于可以超过 n = 2^32 的埃拉托色尼筛法的 Java 实现?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32687386/