[原创]浅析求素数算法

well

非常好，lz功力深厚啊，学习了。
是否可以考虑用 bit文件 代替数组来记录素数呢
另外，如果要产生一个范围内的素数，还可以考虑筛法
有个叫 primegen 的基于 Atkin筛子 的程序，可以在p2-350机器上，8秒产生1-10亿的所有素数
希望进一步讨论

木人

Post by chai2010;1575444
浅析求素数算法
3. 进一步减少判断的范围

   定理: 如果n不是素数, 则n有满足1<d<=sqrt(n)的一个因子d.
   证明: 如果n不是素数, 则由定义n有一个因子d满足1<d<n.
         如果d大于sqrt(n), 则n/d是满足1<n/d<=sqrt(n)的一个因子.

1. 
   
2. bool isPrime(int n)
   
3. {
   
4.     if(n < 2) return false;
   
5.     if(n == 2) return true;
   
6. 
   
7.     for(int i = 3; i*i <= n; i += 2)
   
8.         if(n%i == 0) return false;
   
9. 
   
10.     return true;
    
11. }
    

复制代码

时间复杂度O(sqrt(n)/2), 速度提高O((n-sqrt(n))/2).

这段代码貌似有错误