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

liangbch

在siftPrime.h 中定义L2_CACHE，如果你的电脑L2_CACHE 不是512K，请试着修改为实际值。

shines

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 ms

1. unsigned char bitcount_index_table[] =
2. {
3. 8, 7, 7, 6, 7, 6, 6, 5, 7, 6, 6, 5, 6, 5, 5, 4,
4. 7, 6, 6, 5, 6, 5, 5, 4, 6, 5, 5, 4, 5, 4, 4, 3,
5. 7, 6, 6, 5, 6, 5, 5, 4, 6, 5, 5, 4, 5, 4, 4, 3,
6. 6, 5, 5, 4, 5, 4, 4, 3, 5, 4, 4, 3, 4, 3, 3, 2,
7. 7, 6, 6, 5, 6, 5, 5, 4, 6, 5, 5, 4, 5, 4, 4, 3,
8. 6, 5, 5, 4, 5, 4, 4, 3, 5, 4, 4, 3, 4, 3, 3, 2,
9. 6, 5, 5, 4, 5, 4, 4, 3, 5, 4, 4, 3, 4, 3, 3, 2,
10. 5, 4, 4, 3, 4, 3, 3, 2, 4, 3, 3, 2, 3, 2, 2, 1,
11. 7, 6, 6, 5, 6, 5, 5, 4, 6, 5, 5, 4, 5, 4, 4, 3,
12. 6, 5, 5, 4, 5, 4, 4, 3, 5, 4, 4, 3, 4, 3, 3, 2,
13. 6, 5, 5, 4, 5, 4, 4, 3, 5, 4, 4, 3, 4, 3, 3, 2,
14. 5, 4, 4, 3, 4, 3, 3, 2, 4, 3, 3, 2, 3, 2, 2, 1,
15. 6, 5, 5, 4, 5, 4, 4, 3, 5, 4, 4, 3, 4, 3, 3, 2,
16. 5, 4, 4, 3, 4, 3, 3, 2, 4, 3, 3, 2, 3, 2, 2, 1,
17. 5, 4, 4, 3, 4, 3, 3, 2, 4, 3, 3, 2, 3, 2, 2, 1,
18. 4, 3, 3, 2, 3, 2, 2, 1, 3, 2, 2, 1, 2, 1, 1, 0
19. };
21. // 由于统计个数和你的是反的，要处理一下
22. for (i=0;i<256;i++)
23. bitcount_index_table[i] = 8 - bitcount_index_table[i];
25. static UINT64 GetPrimeFromSiftBuff2(const BYTE *siftBuff,UINT64 begin, UINT64 end,
26. UINT64 currCount, int mode)
27. {
28. assert(begin % 30==0);
29. DWORD endIdx;
31. DWORD i,j;
32. UINT64 pr=currCount;
33. const BYTE maskArray[]={1,2,4,8,16,32,64,128};
34. const BYTE remArray[]={1,7,11,13,17,19,23,29};
36. endIdx=(DWORD)((end-begin)/30-1);
37. if (mode==4)
38. {
39. for (i=0;i<=endIdx;i++)
40. {
41. BYTE keyBYTE;
42. keyBYTE = siftBuff[i];
43. pr += bitcount_index_table[keyBYTE];
44. }
46. i=endIdx+1;
47. for (j=0;j<8;j++)
48. {
49. DWORD tmp=MUL30(i)+(DWORD)begin + remArray[j];
50. if (tmp>end)
51. break;
52. if ( siftBuff[i] & maskArray[j] )
53. {
54. pr++;
55. }
56. }
57. }
58. else if (mode==8)
59. {
60. for (i=0;i<=endIdx;i++)
61. {
62. BYTE keyBYTE;
63. keyBYTE = siftBuff[i];
64. pr += bitcount_index_table[keyBYTE];
65. }
67. i=endIdx+1;
68. for (j=0;j<8;j++)
69. {
70. UINT64 tmp=(UINT64)i *30I64+ begin + (UINT64)remArray[j];
71. if (tmp>end)
72. break;
73. if ( siftBuff[i] & maskArray[j] )
74. {
75. pr++;
76. }
77. }
78. }
79. return pr;
80. }

复制代码

tprime

GxQcn没有公开算法, 所以谁也不知道其中的奥妙所在

无心人

他程序计时存在问题 如果是筛法时间不应该这么少 1亿最小时间大于0.01s

tprime

10亿应该不小于500 ms, 这是我见过的最快筛法 代码过于复杂没看懂

无心人

等俺封存了128乘再和你们混筛法 现在发问题速度太快了 ：） 指不定哪天欠账太多被讨债

tprime

你到处开辟战场能不累吗

无心人

怕什么时候就忘记了 好多东西是一时兴起想起来的 反正这么多人觉得有意思就好了

liangbch

原帖由 无心人 于 2008-3-19 10:00 发表 他程序计时存在问题 如果是筛法时间不应该这么少 1亿最小时间大于0.01s

同感，我也觉得他的计时存在问题，如果是筛法时间不应该这么少。

shines

他计算素数个数应该是用的PI（X）函数，筛法是不可能的，反正只是统计，不比用筛法，这点分得很仔细，不过第一次用会吓一跳