在没想到更好方法之前
俺封闭俺代码，不再优化
下面是测试在PIV上的测试结果（时间单位为毫秒，所有测试均取3次最小值）。
经过进一步的努力，在siftPrime4的基础上改出一个新的版本。主要修改如下，1. 关键部分使用汇编优化，2. 对将筛的过程中用的的素数表 改为压缩的字节数组。(新版所用的文件名为siftPrime5,调用其的测试函数为testSift5）。 在PM上，统计1亿，10亿的素数时，效果明显，大约提速10-15%，但在PIVCPU上，提速效果却不太明些。
np1p3p4p510000007.9791.6524.8970.8971000000075.16412.43713.81511.026100000000782.436143.780130.932132.86810000000008257.1251711.7231546.2831599.733
大家可在你们的机器上测试，看看siftPrime5的表现如何。
哦？
看不明白
p1这么低的时间是什么功能?
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函数的代码。int main(int argc, char* argv[])
{
//testSift1();
//testSift3();
//testSift4();
testSift5();
return 0;
}
声明 62# 中的5.164 应该75.164
呵呵
怪不得呢
你要不是写错了，就忒厉害了
向楼上众高手学习。
62#的CPU是多少啊？
我的2*1.6G的CPU普通筛法用C语言是3900多毫秒，用汇编筛1亿的素数需要1600多毫秒。而您的P1只需0.78秒，快一倍。
不知道哪里出问题了。
你们这里讨论了“高级的分段筛法”太深奥了，看不明白。
同样是普通筛法，我的程序太慢了，没法和P1比阿。liangbch能发下你的p1源吗可以么？
#include <stdio.h>
#include <time.h>
unsigned long S = {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;
m0 = 1 << (i2 & 0x1f);
if (!(n0 & m0))
{
S |= m0;
c0++;
}
i2 += n1;
}
i1++;
i0 = i1 >> 5;
n0 = S;
m0 = 1 << (i1 & 0x1f);
while (n0 & m0)
{
i1++;
m0 <<= 1;
if (m0 == 0)
{
i0++;
n0 = S;
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
段起始数字最好是几个小素数的倍数
则可预选存储部分筛结果而节约时间
...大家都是线性筛法么?
Sieve of Atkin比线性低一点点的筛法