使用筛子查找小于 LONG 数的素数

Question

我必须找出小于或等于给定数 n 的质数个数。我正在使用埃拉托色尼筛法寻找素数。

这是我写的代码：

static int find_prime(int n) {
    boolean[] arr = new boolean[n+1];
    Arrays.fill(arr, true);

for(int i=2;i<=n;i++) {
    if(arr[i]==true) {
        for(int j=2*i; j<=n; j+=i)
            arr[j] = false;
    }
}
int count=0;
for(int i=2;i<=n;i++) {
    //System.out.print(arr[i]+" ");
    if (arr[i] == true)
        count++;
    }
    return count;
}

此代码适用于 integer 个值，但我必须为 long 个数字实现它。 Java 不允许创建 long 大小的数组，因此 boolean[] arr = new boolean[n+1]; 不起作用。有人可以建议我解决这个问题的方法吗？

Answer 1

您将没有足够的内存来表示整个筛子，因为它是以 EB 为单位的。甚至 BitSet is not going to fit all the indexes that you need, because ultimately it uses 一个 long 的数组来存储位。

您可以通过混合方法找到答案：

建造并运行筛子达 Integer.MAX_VALUE
将最多 Integer.MAX_VALUE 个素数收集到 long 个
观察到您可以在达到候选数的平方根时停止检查除数 c
这意味着您已经拥有所有高于 Integer.MAX_VALUE
使用除数数组过滤 Integer.MAX_VALUE 和 n

由于您不需要在 Integer.MAX_VALUE 之后存储额外的素数，因此您的代码不会运行内存不足。

使用筛子查找小于 LONG 数的素数

finding prime numbers less than a LONG number using sieve

java

primes

sieve-of-eratosthenes