logo标签列表

改进质数筛选算法

javaalgorithmprimes
6
我正在尝试编写一个可以生成从1到N的质数（主要用于欧拉计划问题）的Java程序。
目前，我的算法如下：
初始化一个布尔数组（如果N足够大，则使用位数组），使它们都为false，并初始化一个存储找到的质数的int数组。
设置一个整数s等于最小的质数（即2）。
当s <= sqrt（N）时，
在数组/位数组中将s的所有倍数（从s ^ 2开始）设置为true。
找到数组/位数组中下一个最小的值为false的索引，将其用作新的s值。
重复此过程直至结束。
遍历数组/位数组，并将每个为false的值对应的索引放入质数数组中。
现在，我已经尝试跳过非6k + 1或6k + 5形式的数字，但这只使我的速度提高了约两倍，而我已经看到比我的程序运行速度快数个数量级（虽然代码非常复杂），例如此处的程序。
我应该怎么改进呢？
编辑：好吧，这是我的实际代码（用于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毫秒。

2
虽然Java在这里不是最快的选择，但如果您发布（完整但紧凑的）代码，我们可能会发现性能问题。 - Eiko
1
顺便说一下，实现埃拉托斯特尼筛法并不复杂 :) - Waleed Amjad
9个回答
6

当s <= sqrt(N)时，
在这种算法中，人们经常犯的一个错误是没有预先计算平方根。

while (s <= sqrt(N)) {

比起其他技术，它的速度非常非常慢。
int limit = sqrt(N);
while (s <= limit) {

但总体而言，Eiko在他的评论中是正确的。如果您想让人们提供低级别的优化，您必须提供代码。
更新：好的，现在关于您的代码。
您可能会注意到，在您的代码中迭代次数只比“l”略大一些。（您可以将计数器放在第一个“for”循环内部，它将只增加2-3倍）显然，您的解决方案的复杂度不能小于O（l）（您不能少于“l”次迭代）。
真正有区别的是有效地访问内存。请注意，写那篇文章的人试图减少存储大小不仅因为他贪心地使用内存。使紧凑的数组可以更好地利用缓存，从而增加速度。
我只是用int[]替换了boolean[]，并立即获得了两倍的速度增益。（和8倍的内存）而且我甚至没有尝试高效地做到这一点。
更新2： 这很容易。您只需将每个分配a[i]=true替换为a[i/32] |= 1 << (i%32)，将每个读取操作a[i]替换为(a[i/32] & (1 << (i%32))) != 0。当然，将boolean[] a替换为int[] a。
从第一个替换应该清楚它是如何工作的：如果f(i)为true，则整数a[i/32]中有一个位1，在位置i%32（正如您所知，Java中的int恰好有32位）。
您可以进一步将i/32替换为i>>5，将i%32替换为i&31。您还可以预先计算数组中0到31之间每个j的所有1<
但不幸的是，我认为在Java中，您无法接近C。更不用说，那个家伙使用了许多其他棘手的优化，我同意他的代码如果加上注释会更有价值。
sqrt(N) 可能使用自然对数来计算值，这会比执行 while (ss < N) 慢。或者预先计算 ss 并使用它。 - Waleed Amjad
1
不是，我预先计算了 N 的平方根。 - Rob
是的，你说得对，但我认为用while(n*n <= l)会比while(n <= sqrt)略快一点。 - Waleed Amjad
尝试使用上述代码（对于N = 1E7）进行了测试；速度没有明显变化。 - Rob
我使用位运算技巧，获得了3倍的速度提升。这太棒了:D - Rob
优化器不会负责预计算平方根吗？ - Celeritas
3

使用BitSet可以节省内存。筛选算法相当简单，因此您只需在BitSet上“设置”位位置，然后迭代以确定质数。

使用BitSet实际上更慢。使用new BitSet(l+1)进行初始化所需的时间是new boolean[l+1]的两倍，而循环比使用boolean[]稍微慢一些。我认为这种减速是由于方法调用set(i)、get(i)和nextClearBit(i)的开销引起的，而不是从数组访问值。 - rudi-moore
注意我没有提到速度 :P - gpampara
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;
}
有趣...对我来说，它提供了<2倍的加速（350毫秒-> 190毫秒） 但这仍然很好，特别是考虑到它可以与其他优化结合使用。谢谢！^_^ - Rob
2
以下是我的欧拉工程库的内容...它是埃拉托色尼筛法的一个小变体...我不确定，但我认为它被称为欧拉筛法。
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;
}
1

最近我为了好玩写了一个简单的筛子实现，使用了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（例如1000万，用时为0.077479秒）时，我们比OP获得更快的结果。

1
你可以在检测质数的同时，将相应的索引放入质数数组中，这样就不用再遍历一遍数组了。但目前我能想到的就只有这些了。
我不确定在我上面发布的代码中是否可能实现这一点。你能详细说明一下吗？ - Rob
我在你的代码之前发布了这个。所以我不会知道。我只是根据你的描述来做的。 - evantravers
0

这是我的埃拉托斯特尼筛法代码，实际上这是我能做到的最有效率的：

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<MAX;j+=2*i)
            p[j]=1;
    }
    for(i=3;i<MAX;i+=2)
    {
        if(p[i]==0)
            prime[k++]=i;
    }
    return;
}
0

我敢打赌，当处理位时，Java的性能肯定很差......从算法上讲，你指出的链接应该足够了。

问题是我不知道链接中发生了什么。 - Rob
你具体不明白什么？ - Alexandre C.
在 primes_sieve.c 链接中间位置的源代码似乎几乎无法阅读 <.< - Rob
该 HTML 页面包含有用的信息。 - Alexandre C.
我原本认为jvm不知道可能存在的特殊cpu指令，比如popcount，但现在我认为我错了：http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Integer.html - Alexandre C.
显示剩余2条评论
0
生成质数的方法不仅仅是顺序应用素性检查，还有更高效的方法。 - Hank Gay
当然，但是这个“如何生成前N个质数”的问题并不是什么新问题，而且谷歌搜索足以找到各种改进的方法。 - Peter G.
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接