改进主筛算法

我正在尝试制作一个不错的Java程序，从1到N生成素数（主要用于Project Euler问题）。

目前，我的算法如下：

初始化一个布尔数组（如果N足够大则初始化为bitarray），因此它们都是假的，并且存储了一组用于存储素数的int。

设置一个整数，s等于最低素数，（即2）

s是<= sqrt（N）

在数组/ bitarray中将s的所有倍数（从s ^ 2开始）设置为true。

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

ENDWHILE。

遍历数组/ bitarray，对于每个false的值，将相应的索引放在primes数组中。

现在，我试过跳过不是6k + 1或6k + 5forms的数字，但这只能让我加速~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） '迭代）。

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

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

UPDATE2
这很简单。 您只需用a[i/32] |= 1 << (i%32)替换每个赋值a[i] = true ，并且每个读取操作a[i]用(a[i/32] & (1 << (i%32))) != 0 。 并且boolean[] a显然是int[] a 。

从第一次替换开始，它应该清楚它是如何工作的：如果f(i)为真，那么整数a[i/32]的位1 ，位置i%32 （Java中的int恰好是32位，如你所知）。

你可以进一步用i >> 5替换i/32 ，用i&31替换i%32 。 您还可以为数组中0到31之间的每个j预计算所有1 << j 。

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

Answer 2

使用BitSet将使用更少的内存。 Sieve算法相当简单，因此您可以简单地“设置” BitSet上的位位置，然后迭代以确定素数。

Answer 3

您是否也在跳过不是6k + 1和6k + 5forms的数字时使数组变小？ 我只测试了忽略2kforms的数字，这给了我~4倍加速（440毫秒 – > 120毫秒）：

 int l = 10000000, n = 1, sqrt = (int) Math.sqrt(l); int m = l/2; boolean[] nums = new boolean[m + 1]; int[] primes = new int[664579]; int i, k; while (n <= sqrt) { int x = (n<<1)+1; for (i = n+x; i <= m; nums[i] = true, i+=x); for (n++; nums[n]; n++); } primes[0] = 2; for (i = 1, k = 1; i < nums.length; i++) { if (!nums[i]) primes[k++] = (i<<1)+1; } 

Answer 4

以下内容来自我的Euler图书馆……它是Eratosthenes筛子的一个微小的变化……我不确定，但我认为它叫做Euler Sieve。

1）它使用BitSet（因此是存储器的1/8）2）仅使用奇数位的位集…（另外1/2因此1/16）

注意：内部循环（对于倍数）从“n * n”开始而不是“2 * n”，并且增量“2 * n”的倍数仅被交叉….因此加速。

 private void beginSieve(int mLimit) { primeList = new BitSet(mLimit>>1); primeList.set(0,primeList.size(),true); int sqroot = (int) Math.sqrt(mLimit); primeList.clear(0); for(int num = 3; num <= sqroot; num+=2) { if( primeList.get(num >> 1) ) { int inc = num << 1; for(int factor = num * num; factor < mLimit; factor += inc) { //if( ((factor) & 1) == 1) //{ primeList.clear(factor >> 1); //} } } } } 

这是检查一个数字是否为素数的函数…

 public boolean isPrime(int num) { if( num < maxLimit) { if( (num & 1) == 0) return ( num == 2); else return primeList.get(num>>1); } return false; } 

Answer 5

您可以在检测它们时执行“将相应的索引放在primes数组中”的步骤，然后在数组中运行，但这就是我现在能够想到的全部内容。

Answer 6

我最近编写了一个简单的筛选器实现它使用BitSet的乐趣（每个人都说不是，但它是有效存储大量数据的最佳方式）。 对我来说表现似乎相当不错，但我仍在努力改进它。

 public class HelloWorld { private static int LIMIT = 2140000000;//Integer.MAX_VALUE broke things. private static BitSet marked; public static void main(String[] args) { long startTime = System.nanoTime(); init(); sieve(); long estimatedTime = System.nanoTime() - startTime; System.out.println((float)estimatedTime/1000000000); //23.835363 seconds System.out.println(marked.size()); //1070000000 ~= 127MB } private static void init() { double size = LIMIT * 0.5 - 1; marked = new BitSet(); marked.set(0,(int)size, true); } private static void sieve() { int i = 0; int cur = 0; int add = 0; int pos = 0; while(((i<<1)+1)*((i<<1)+1) < LIMIT) { pos = i; if(marked.get(pos++)) { cur = pos; add = (cur<<1); pos += add*cur + cur - 1; while(pos < marked.length() && pos > 0) { marked.clear(pos++); pos += add; } } i++; } } private static void readPrimes() { int pos = 0; while(pos < marked.length()) { if(marked.get(pos++)) { System.out.print((pos<<1)+1); System.out.print("-"); } } } } 

使用较小的LIMIT（比如10,000,000，花费0.077479），我们得到的结果比OP快得多。

Answer 7

我敢打赌，在处理比特时，java的表现很糟糕……从算法来看，你指出的链接应该足够了

Answer 8

你有没有尝试谷歌搜索，例如“java prime numbers”。 我做了并挖掘了这个简单的改进：

http://www.anyexample.com/programming/java/java_prime_number_check_%28primality_test%29.xml

当然，你可以在谷歌找到更多。

Answer 9

这是我的Erastothenes筛选器的代码，这实际上是我能做的最有效的：

 final int MAX = 1000000; int p[]= new int[MAX]; p[0]=p[1]=1; int prime[] = new int[MAX/10]; prime[0]=2; void sieve() { int i,j,k=1; for(i=3;i*i<=MAX;i+=2) { if(p[i]) continue; for(j=i*i;j