Eratosthenes筛选的Java实现可以超过n = 2 ^ 32？ [英] Java implementation of Sieve of Eratosthenes that can go past n = 2^32?

问题描述

目前我有这个限制为n< 2 ^ 32-1。鉴于数组中元素的限制，我不能完全确定如何进一步扩展限制。

Currently I have this prime generator that is limited to n < 2^32-1. I'm not entirely sure how I could expand the limit further, given the limit of elements in an array.

Sieve：

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？

How could I modify this to go past n = 2^32-1?

推荐答案

你可以使用一个数组 BitSet 表示长位集的对象。以下是完整的示例：

You may use an array of BitSet objects to represent long bit-set. Here's the complete example:

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 这是正确的低于4亿的素数根据Wolfram Alpha 。如果你有足够的内存，你可以尝试设置更大的N.

This program for N = 4_000_000_000L takes around 512Mb of memory, works couple of minutes and prints 189961812 which is correct number of primes below 4 billions according to Wolfram Alpha. If you have enough RAM, you may try setting even bigger N.

这篇关于Eratosthenes筛选的Java实现可以超过n = 2 ^ 32？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！