素数搜索器

981013

Prime.tar.gz (1 KB, 下载次数: 14)

2014-5-3 14:11 上传

点击文件名下载附件

这是我自己做的素数搜索器。
理论上来说可以把2～unsigned long long最大值的素数全找到。
发布的文件里有源码，还附上了Makefile
make（或用C++编译器编译）后有个PrimeFinder是主程序，使用方法：在终端或cmd中运行（在windows系统上，点一下就行），然后输入需要找到的最大数的值，然后程序就会把2～你所需的数中的素数打印在Primes.txt里
Primes.txt不要删除
因为当搜索到了很多素数后，用文本编辑器打开Primes.txt变得需要耗费大量时间，所以有ViewLast这一个程序帮我们迅速查看当前文件里的最后（也是最大的一个素数）这个程序运行时需要由操作系统传入文件名作为参数

981013

请各位高手指导（优化）

winkill

{:soso__3669389859068460655_4:}

李掌柜

981013 发表于 2014-5-3 14:33
请各位高手指导（优化）

关于素数的优化，《编程珠玑（续）》中第一章第一节的P6算是最优化的吧~~！

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";就可以了