我正在尝试制作一个不错的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++] …