10秒内计算出1亿素数表, 不输出

无心人

在没想到更好方法之前
俺封闭俺代码，不再优化

liangbch

下面是测试在PIV上的测试结果（时间单位为毫秒，所有测试均取3次最小值）。

经过进一步的努力，在siftPrime4的基础上改出一个新的版本。主要修改如下，1. 关键部分使用汇编优化，2. 对将筛的过程中用的的素数表 改为压缩的字节数组。(新版所用的文件名为siftPrime5,调用其的测试函数为testSift5）。 在PM上，统计1亿，10亿的素数时，效果明显，大约提速10-15%，但在PIVCPU上，提速效果却不太明些。

n	p1	p3	p4	p5
1000000	7.979	1.652	4.897	0.897
10000000	75.164	12.437	13.815	11.026
100000000	782.436	143.780	130.932	132.868
1000000000	8257.125	1711.723	1546.283	1599.733

大家可在你们的机器上测试，看看siftPrime5的表现如何。

无心人

哦？
看不明白
p1这么低的时间是什么功能?

liangbch

       siftPrime1                siftPrime2                siftPrime3
     1亿   0.78秒                0.172秒                        0.125秒
    10亿   8.25秒                1.86秒                         1.547秒
    100亿  92.78秒                21.7秒                        18.4秒

p1:即 47# 提到的siftPrime1, 这个版本是最普通的算法，采用byte数组，没有使用任何技巧，所有速度很慢。
p1,p3,p4,p5 对应于 在main函数中 调用 testSift1，testSift3，testSift4，testSift5 这几个版本的执行结果.你可以将这几个函数调用分别打开，在你的电脑上测试一下，看看效果如何，下面是main函数的代码。

1. int main(int argc, char* argv[])
   
2. {
   
3.         //testSift1();
   
4.         //testSift3();
   
5.         //testSift4();
   
6.         testSift5();
   
7.         return 0;
   
8. }

复制代码

liangbch

声明 62# 中的5.164 应该75.164

无心人

呵呵
怪不得呢
你要不是写错了，就忒厉害了

k9s

向楼上众高手学习。
62#的CPU是多少啊？
我的2*1.6G的CPU普通筛法用C语言是3900多毫秒，用汇编筛1亿的素数需要1600多毫秒。而您的P1只需0.78秒，快一倍。
不知道哪里出问题了。
你们这里讨论了“高级的分段筛法”太深奥了，看不明白。

k9s

同样是普通筛法，我的程序太慢了，没法和P1比阿。liangbch能发下你的p1源吗可以么？　

#include <stdio.h>
#include <time.h>

unsigned long S [1562500] = {0};

unsigned long sieve ()
{
        unsigned long c0 = 0,i1,n1,i2,n2,i0,n0,m0;
        n1 = 3; i1 = 1;
        while ( n1 < 10000 )
        {
                n2 = n1 * n1;
                i2 = n2 >> 1;
                while ( i2 < 50000000 )
                {
                        i0 = i2 >> 5; n0 = S[i0];
                        m0 = 1 << (i2 & 0x1f);
                        if (!(n0 & m0))
                        {
                                S[i0] |= m0;
                                c0++;
                        }
                        i2 += n1;
                }
                i1++;
                i0 = i1 >> 5;
                n0 = S[i0];
                m0 = 1 << (i1 & 0x1f);
        while (n0 & m0)
        {
                        i1++;
                        m0 <<= 1;
                        if (m0 == 0)
                        {
                                i0++;
                                n0 = S[i0];
                                m0 = 1;
                        }
        }
            n1 = (i1 << 1) + 1;
        }
    return 50000000 - c0;
}

int main()
{
        clock_t t1 = clock(),t2;
        unsigned long c = sieve();
        t2 = clock();
        printf("%d --> time : %d\n",c,t2-t1);
    system("PAUSE");
    return 0;
}

/************************************************************
E:\worker>shai
5761455 --> time : 2230
Press any key to continue . . .
************************************************************/

无心人

呵呵
你先把算法作好了
再考虑汇编
算法不优秀
汇编白优化
主要考虑
分段大小不要超过CPU L2 Cache
段起始数字最好是几个小素数的倍数
则可预选存储部分筛结果而节约时间

Mgccl

...大家都是线性筛法么?
Sieve of Atkin比线性低一点点的筛法