在siftPrime.h 中定义L2_CACHE，如果你的电脑L2_CACHE 不是512K，请试着修改为实际值。
to liangbch:
由于我们的代码实际上都没有输出素数，tprime的也一样，所以我修改了一下你的代码，否则没有可比性
统计素数的个数而不输出素数表，而我的代码里有2种方式，一种是仅筛法和统计每分段的素数，另一种是保留所有的bit位数组，且统计所有素数个数，程序最后可以检验0-N任何一个数是否为素数，不过计算2-2^30两者相差仅0.2秒而已。
你的代码比我的稍快，不过最快的应该还是GxQcn的。
改进后，仅统计个数
sift prime from 2 to n
n=?(n=0 will exit)1073741824
Total 54400028 in 1073741824
It take 1656 ms
sift prime from 2 to n
n=?(n=0 will exit)2147483648
Total 105097565 in 2147483648
It take 3500 msunsigned char bitcount_index_table[] =
{
8, 7, 7, 6, 7, 6, 6, 5, 7, 6, 6, 5, 6, 5, 5, 4,
7, 6, 6, 5, 6, 5, 5, 4, 6, 5, 5, 4, 5, 4, 4, 3,
7, 6, 6, 5, 6, 5, 5, 4, 6, 5, 5, 4, 5, 4, 4, 3,
6, 5, 5, 4, 5, 4, 4, 3, 5, 4, 4, 3, 4, 3, 3, 2,
7, 6, 6, 5, 6, 5, 5, 4, 6, 5, 5, 4, 5, 4, 4, 3,
6, 5, 5, 4, 5, 4, 4, 3, 5, 4, 4, 3, 4, 3, 3, 2,
6, 5, 5, 4, 5, 4, 4, 3, 5, 4, 4, 3, 4, 3, 3, 2,
5, 4, 4, 3, 4, 3, 3, 2, 4, 3, 3, 2, 3, 2, 2, 1,
7, 6, 6, 5, 6, 5, 5, 4, 6, 5, 5, 4, 5, 4, 4, 3,
6, 5, 5, 4, 5, 4, 4, 3, 5, 4, 4, 3, 4, 3, 3, 2,
6, 5, 5, 4, 5, 4, 4, 3, 5, 4, 4, 3, 4, 3, 3, 2,
5, 4, 4, 3, 4, 3, 3, 2, 4, 3, 3, 2, 3, 2, 2, 1,
6, 5, 5, 4, 5, 4, 4, 3, 5, 4, 4, 3, 4, 3, 3, 2,
5, 4, 4, 3, 4, 3, 3, 2, 4, 3, 3, 2, 3, 2, 2, 1,
5, 4, 4, 3, 4, 3, 3, 2, 4, 3, 3, 2, 3, 2, 2, 1,
4, 3, 3, 2, 3, 2, 2, 1, 3, 2, 2, 1, 2, 1, 1, 0
};
// 由于统计个数和你的是反的，要处理一下
for (i=0;i<256;i++)
bitcount_index_table = 8 - bitcount_index_table;
static UINT64 GetPrimeFromSiftBuff2(const BYTE *siftBuff,UINT64 begin, UINT64 end,
UINT64 currCount, int mode)
{
assert(begin % 30==0);
DWORD endIdx;
DWORD i,j;
UINT64 pr=currCount;
const BYTE maskArray[]={1,2,4,8,16,32,64,128};
const BYTE remArray[]={1,7,11,13,17,19,23,29};
endIdx=(DWORD)((end-begin)/30-1);
if (mode==4)
{
for (i=0;i<=endIdx;i++)
{
BYTE keyBYTE;
keyBYTE = siftBuff;
pr += bitcount_index_table;
}
i=endIdx+1;
for (j=0;j<8;j++)
{
DWORD tmp=MUL30(i)+(DWORD)begin + remArray;
if (tmp>end)
break;
if( siftBuff & maskArray )
{
pr++;
}
}
}
else if (mode==8)
{
for (i=0;i<=endIdx;i++)
{
BYTE keyBYTE;
keyBYTE = siftBuff;
pr += bitcount_index_table;
}
i=endIdx+1;
for (j=0;j<8;j++)
{
UINT64 tmp=(UINT64)i *30I64+ begin + (UINT64)remArray;
if (tmp>end)
break;
if( siftBuff & maskArray )
{
pr++;
}
}
}
return pr;
}
GxQcn没有公开算法, 所以谁也不知道其中的奥妙所在
他程序计时存在问题
如果是筛法时间不应该这么少
1亿最小时间大于0.01s
10亿应该不小于500 ms,这是我见过的最快筛法
代码过于复杂没看懂
等俺封存了128乘再和你们混筛法
现在发问题速度太快了
：）
指不定哪天欠账太多被讨债
你到处开辟战场能不累吗
怕什么时候就忘记了
好多东西是一时兴起想起来的
反正这么多人觉得有意思就好了
原帖由 无心人 于 2008-3-19 10:00 发表 http://images.5d6d.net/dz60/common/back.gif
他程序计时存在问题
如果是筛法时间不应该这么少
1亿最小时间大于0.01s
同感，我也觉得他的计时存在问题，如果是筛法时间不应该这么少。
他计算素数个数应该是用的PI（X）函数，筛法是不可能的，反正只是统计，不比用筛法，这点分得很仔细，不过第一次用会吓一跳