改进主筛算法

Question

我正在尝试制作一个不错的Java程序,从1到N生成素数(主要用于Project Euler问题).

目前,我的算法如下:

初始化一个布尔数组(如果N足够大则初始化为bitarray),因此它们都是假的,并且存储了一组用于存储素数的整数.

设置一个整数,s等于最低素数,(即2)

s是<= sqrt(N)

在数组/位阵列中将s的所有倍数(从s ^ 2开始)设置为true.

找到array/bitarray中的下一个最小索引,该索引为false,将其用作s的新值.

ENDWHILE.

遍历数组/位阵列,对于每个假的值,将相应的索引放在primes数组中.

现在,我试过跳过不是6k + 1或6k + 5形式的数字,但这只能让我加速~2倍,而我看到程序运行的速度比我的速度快(虽然非常复杂)代码),例如这里的那个

我该怎么做才能改善？

编辑:好的,这是我的实际代码(对于1E7的N):

int l = 10000000, n = 2, sqrt = (int) Math.sqrt(l);
boolean[] nums = new boolean[l + 1];
int[] primes = new int[664579];

while(n <= sqrt){
    for(int i = 2 * n; i <= l; nums[i] = true, i += n);
    for(n++; nums[n]; n++);
}

for(int i = 2, k = 0; i < nums.length; i++) if(!nums[i]) primes[k++] = i;

在我的2.0GHz机器上运行大约350ms.

Answer 1

当s <= sqrt(N)时,
人们经常在这种算法中做的一个错误就是不预先计算平方根.

while (s <= sqrt(N)) {

比...慢得多

int limit = sqrt(N);
while (s <= limit) {

但总的来说,Eiko的评论是正确的.如果您希望人们提供低级优化,您必须提供代码.

更新好的,现在关于你的代码.

您可能会注意到代码中的迭代次数比"l"略大.(你可以把计数器放在第一个'for'循环中,它只会大2-3倍)显然,你的解决方案的复杂性不能低于O(l)(你不能低于'l) '迭代).

真正有用的是有效地访问内存.请注意,写这篇文章的人试图减少存储空间,不仅仅是因为他的内存贪婪.制作紧凑型阵列可以让您更好地使用缓存,从而提高速度.

我刚用int []替换了boolean []并立即获得了x2速度增益.(和8倍内存)我甚至没有尝试有效地做到这一点.

update2
这很容易.您只需更换每一个分配a[i] = true与a[i/32] |= 1 << (i%32) 每个读操作a[i]有(a[i/32] & (1 << (i%32))) != 0.并boolean[] a用int[] a,效果显着.

从第一次替换它应该清楚它是如何工作的:如果f(i)是真的,那么1在整数中有一个位a[i/32],在位置i%32(int在Java中正好有32位,如你所知).

你可以更进一步,取代i/32用i >> 5,i%32用i&31.您还可以为1 << j阵列中0到31之间的每个j 预计算全部.

但遗憾的是,我不认为在Java中你可以接近C.更不用说,那家伙使用了许多其他棘手的优化,我同意如果他发表评论,他的价值可能会更高.

Answer 2

我敢打赌，在处理位时，java 的性能很糟糕...从算法上讲，您指出的链接应该足够了