java改进素数筛算法

Question

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

目前，我的算法如下：

初始化一个布尔数组（如果N足够大，则初始化一个位数组），使其全部为false，并初始化一个int数组以存储找到的素数

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

而s是<；=sqrt（N）

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

在数组/位数组中找到下一个最小的索引，该索引为false，将其用作s的新值

结束

遍历数组/位数组，对于每个为false的值，将相应的索引放入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机器上运行大约350毫秒

Answer 1

你可以在检测素数数组时执行“将相应的索引放入素数数组”的步骤，对数组进行遍历，但这就是我现在所能想到的

Answer 2

在跳过非6k+1和6k+5形式的数字时，是否也使数组变小了？ 我只在忽略表格2k的数字的情况下进行了测试，这使我的速度提高了约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 3

我最近编写了一个简单的sieve实现，目的是利用位集（每个人都说不要，但这是高效存储海量数据的最佳现成方法）。对我来说，它的表现似乎相当不错，但我仍在努力提高它

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("-");
            }
        }
    }
}

在较小的限制下（比如10000000，需要0.077479秒），我们得到的结果比OP快得多

Answer 4

以下内容来自我的项目Euler库。。。这是埃拉托斯坦筛的细微变化。。。我不确定，但我认为它被称为欧拉筛

1）它使用一个位集（因此是内存的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

而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倍的内存）而我甚至没有尝试有效地完成它

更新2
这很简单。只需将每个赋值a[i] = true替换为a[i/32] |= 1 << (i%32)，将每个读取操作a[i]替换为(a[i/32] & (1 << (i%32))) != 0。显然，还有{}和{}

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

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

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

Answer 6

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