素数搜索器

rosynirvana

这个，没考虑用筛法吗
筛出1亿之内的质数1秒钟上下的事情

rosynirvana

1. #include <bitset>
   
2. #include <iostream>
   
3. #include <ios>
   
4. #include <vector>
   
5. #include <algorithm>
   
6. 
   
7. using std::bitset;
   
8. using std::vector;
   
9. 
   
10. bitset<100000000> buf;
    
11. vector<int> prime_table;
    
12. 
    
13. void init();
    
14. 
    
15. int main(int argc, char **argv)
    
16. {
    
17.         init();
    
18.         std::cout << prime_table.size() << " prime number cached, the max one is "
    
19.                 << prime_table.back() << "\n";
    
20.                
    
21.         int required;
    
22.         std::cout << "Max value?" << "\n";
    
23.         std::cin >> required;
    
24.        
    
25.         if(required <= 100000000){
    
26.                 vector<int>::iterator iter, up =
    
27.                         std::upper_bound(prime_table.begin(), prime_table.end(), required);
    
28.                 for(iter=prime_table.begin(); iter!=up; ++iter)
    
29.                         std::cout << *iter << " ";
    
30.         }
    
31.         else
    
32.                 std::cout << "Too big for a regular PC! Maybe next version!\n";
    
33.                
    
34.         return 0;
    
35. }
    
36. 
    
37. void init()
    
38. {
    
39.         std::ios_base::sync_with_stdio(false);
    
40.        
    
41.         buf[0] = buf[1] = 1;
    
42.         int i = 2;
    
43.         for(i=2; i<10000; ++i)
    
44.                 if(buf[i] == 0){
    
45.                         prime_table.push_back(i);
    
46.                         buf[i] = 1;
    
47.                         for(int j=i*i; j<100000000; j+=i)
    
48.                                 buf[j] = 1;
    
49.                 }
    
50.         for(i=9999; i<100000000; i+=2)
    
51.                 if(buf[i] == 0)
    
52.                         prime_table.push_back(i);
    
53. }

复制代码

很久之前提到的筛法代码
因为用的是bitset，编译要加-O2，不然印象中要10s以上的才能计算出一亿之内的质数

另外不要用endl，这东西的含义是换行且刷新控制台，速度很慢的
如果只是要换行应该std::cout << "\n";就可以了