刚看酷壳里的关于求素数的算法，感觉比我以前写的效率高多了。但酷壳里的判断是否是质数的函数稍微有点问题，没有判断负数，零和1的情况。我自己补充一下，同时对于他们如何想到用平方根这种方法判断感到很好奇。
#include <iostream> using namespace std; bool IsPrimeNum(int nNum) { if(nNum < 2) { return false; } for(int d =2; (d*d) <= nNum; d++) { if(!(nNum % d)) { return false; } } return true; } int main() { for(int i = 50; i > 0; --i) { if(IsPrimeNum(i)) { cout<<i<<endl; } } return 0; }
现简单分析一下这个算法，初始化数列是
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
第一次去掉所有被2整除的
2 3 5 7 9 11 13 15 17 19 21 23 25 27 29
第二次去掉所有被3整除的
2 3 5 7 11 13 19 23 25 29
第三次去掉所有被5整除的(去2的时候去掉4了)
2 3 5 7 11 13 19 23 29
算法不太懂，要想达到上面三次就遍历出来，肯定是记录每次过滤出的数，通过空间换取时间的方式吧。
