求10的10次方以内的素数，怎么能在几小时内算出来结果？

prolj

原帖由 tyc611 于 2009-4-22 23:45 发表

几个0不重要，我只是觉得测试结果很有趣：
(1) long long vs int
(2) VC vs GCC
你再看看结果

误差？还是两个差距大？明示

obkof

wonderful!!!!

令，为什么我不能下载附件啊，提示为”对不起，请不要从外部链接下载本论坛的附件。“

原帖由 lbaby 于 2009-4-22 22:59 发表
http://blog.csdn.net/lbaby/archive/2009/04/22/4101835.aspx

使用lbaby筛，求10亿之内的所有素数（Yet Another Algorithm)


1，第一步思考：

只有个位数是 1 ,3 ,7 , 9 的数才可能是素数 －－ （结 ...

给个理由先

原帖由 lbaby 于 2009-4-22 22:59 发表
http://blog.csdn.net/lbaby/archive/2009/04/22/4101835.aspx

使用lbaby筛，求10亿之内的所有素数（Yet Another Algorithm)


1，第一步思考：

只有个位数是 1 ,3 ,7 , 9 的数才可能是素数 －－ （结 ...

lbaby ,试下

ubuntuer

原帖由 obkof 于 2009-4-23 01:52 发表
wonderful!!!!

令，为什么我不能下载附件啊，提示为”对不起，请不要从外部链接下载本论坛的附件。“

me too

皇家救星

写了一个，测试了一下，算10^9耗时50+秒

这还是在比较高端的机器上跑的结果，真不知7秒是怎么出来的

1. 
   
2. 
   
3. #include "stdafx.h"
   
4. 
   
5. 
   
6. #define LEN (sizeof(char) * 8)
   
7. #define GETBIT(buffer, offset, bit) ( buffer[offset] & ( 128 >> bit ) )
   
8. #define SETBIT(buffer, n) ( buffer[n / LEN] |= ( 128 >> (n % LEN) ) )
   
9. 
   
10. 
    
11. int GetPrime()
    
12. {
    
13.         size_t MAX_NUM = 1e1;
    
14.         size_t BORDER = (size_t) sqrt( (double) MAX_NUM);
    
15.         size_t count = 0;
    
16. 
    
17.         //分配空间并置0，如果分配空间不成功则需加大虚拟内存
    
18.         char *buffer = new char [MAX_NUM / LEN + 1];
    
19.         if (buffer == NULL)
    
20.         {
    
21.                 cerr << "new faile!" << endl;
    
22.                 return 1;
    
23.         }
    
24.         memset(buffer, 0, MAX_NUM / LEN + 1);
    
25.         buffer[0] = (char) 128;  //1不是素数，也不是合数
    
26. 
    
27.         size_t  bit = 2, offset = 0;
    
28. 
    
29.         //筛法找素数
    
30.         for (size_t i = 2; i <= MAX_NUM; i++, bit++)
    
31.         {
    
32.                 //每8位进一个单元格
    
33.                 if ( bit == LEN )
    
34.                 {
    
35.                         offset++;
    
36.                         bit = 0;
    
37.                 }
    
38.                
    
39.                 //找到一个素数
    
40.                 if (!GETBIT(buffer, offset, bit))
    
41.                 {
    
42.                         count++;
    
43.                        
    
44.                         //所有能整除该素数的数全是合数
    
45.                         for (size_t j = 2 * i; j <= MAX_NUM; j += i)
    
46.                         {
    
47.                                 SETBIT(buffer, j);
    
48.                         }
    
49. 
    
50.                         DEBUG_COUT(cout << i << ", ");
    
51.                 }
    
52.         }
    
53. 
    
54.         DEBUG_COUT(cout << "\b\b " << endl);
    
55. 
    
56.         cout << "total prime " << count << endl;
    
57. 
    
58.         //释放空间
    
59.         delete []buffer;
    
60. 
    
61.         return 0;
    
62. };
    
63. 
    
64. int main(int argc, char *argv[])
    
65. {
    
66.         RUNTIME(GetPrime, ());
    
67. 
    
68.         return 0;
    
69. }
    
70. 
    

复制代码

皇家救星

$time prime

total prime 50847535
GetPrime() takes 53765106

real    0m54.53s
user    0m53.77s
sys     0m0.00s

testab

"？？？？没看明白..........
那10的2次方以内的素数，是不是只要在10的1次方以内找就可以了，11，13，17呢？？ "

2*3*5*7=210 >100=10的2次方
所以 11/2  11/3 11/5 11/7 都没除开 所以是质数
    例如 57/2 没除开 57/3=19 所以是合数。

testab

是的.

lbaby

原帖由 ubuntuer 于 2009-4-23 10:31 发表

me too

木有登陆，

zliming

原帖由 lbaby 于 2009-4-22 22:59 发表
http://blog.csdn.net/lbaby/archive/2009/04/22/4101835.aspx

使用lbaby筛，求10亿之内的所有素数（Yet Another Algorithm)


1，第一步思考：

只有个位数是 1 ,3 ,7 , 9 的数才可能是素数 －－ （结 ...

B,只存储个位数是 1，3，7，9的整数
这个其实和去掉偶数的方法一样，前期干掉一堆数。比去偶数法再删一个 个位数为5的
去偶数后第二次筛可以全干掉个位为5的
剩下的是否 乘还是加法筛没有看出很大差别

还是我理解错误，请直接贴一下代码。学习并测试一下