使用sieve查找小于长整数的质数

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;
}

这段代码适用于< code>integer值，但是我必须为< code>long数实现它。而Java不允许创建< code>long大小的数组，所以< code > boolean[]arr = new boolean[n 1]；不起作用。有人能建议我解决这个问题的方法吗？

Answer 1

您没有足够的内存来表示整个筛子，因为它以艾字节为单位。即使BitSet也不会适合您需要的所有索引，因为最终它使用long数组来存储位。

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

< li >构建并运行一个高达< code >整数的筛子。MAX_VALUE < li >采集高达< code >整数的质数。MAX_VALUE转换为< code>longs数组 < li >注意，当达到候选数字< code>c的平方根时，您可以停止检查除数 < li >这意味着您已经有了大于< code>Integer值的所有可能的除数。MAX_VALUE < li >使用除数数组筛选< code >整数之间的数字。最大值和< code>n

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