目前,我的算法如下：
初始化一个布尔数组(如果N足够大则初始化为bitarray),因此它们都是假的,并且存储了一组用于存储素数的整数.
设置一个整数,s等于最低素数,(即2)
s是< = sqrt(N) 在数组/位阵列中将s的所有倍数(从s ^ 2开始)设置为true. 找到array / bitarray中的下一个最小索引,该索引为false,将其用作s的新值. ENDWHILE. 遍历数组/位阵列,对于每个假的值,将相应的索引放在primes数组中. 现在,我尝试跳过不是6k 1或6k 5形式的数字,但这只能让我加速〜2倍,而我看到程序的运行速度比我的速度快(尽管代码非常复杂),如一个here
我该怎么做才能改善？
编辑：好的,这是我的实际代码(对于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.
解决方法
人们在这种算法中经常犯的一个错误就是不预先计算平方根.
while (s <= sqrt(N)) {
比…慢得多
int limit = sqrt(N);
while (s <= limit) {
但总的来说,Eiko的评论是正确的.如果您希望人们提供低级优化,您必须提供代码.
更新好的,现在关于你的代码.
您可能会注意到代码中的迭代次数比“l”略大. (你可以把计数器放在第一个’for’循环中,它只会大2-3倍)显然,你的解决方案的复杂性不能低于O(l)(你不能低于’l) ‘迭代).
真正有用的是有效地访问内存.请注意,写这篇文章的人试图减少存储空间,不仅仅是因为他的内存贪婪.制作紧凑型阵列可以让您更好地使用缓存,从而提高速度.
我刚用int []替换了boolean []并立即获得了x2速度增益. (和8倍内存)我甚至没有尝试有效地做到这一点.
UPDATE2这很简单.您只需用[i / 32] | = 1<<来替换每个赋值a [i] = true (i2)和每个读操作a [i]与(a [i / 32]&(1<(i2)))！= 0.并且boolean [] a与int [] a,显然. 从第一个替换它应该清楚它是如何工作的：如果f(i)为真,那么在整数a [i / 32]中的位1,在位置i2(Java中的int恰好是32位,就像你一样知道). 您可以更进一步,用i>>替换i / 32 5,i2与i& 31.您还可以预先计算所有1<< j为数组中0到31之间的每个j. 但遗憾的是,我不认为在Java中你可以接近C.更不用说,那家伙使用了许多其他棘手的优化,我同意如果他发表评论,他的价值可能会更高.
