求质数

想到当初实习和转正的面试中都遇到了算质数这道题，又都没有很好的写出来，就很懊恼，所以想当个好的程序媛，先从这个问题开始吧。

“对于给定的整数 N，求出所有小于 N 的质数，并打印出来。”

当时听到这个问题，第一反应肯定是从2到N-1的除，如果都不能整除就是质数，然后我就这么做了……好吧，不要嘲笑我，就算是这样代码也写得磕磕绊绊，Java和c++混在一起的感觉。

今天搜“求质数”的时候看到这么一篇文章，http://blog.csdn.net/net_assassin/article/details/8960572，我所想到的方法按10分只能得1分，好吧。2到N的开方的方法也听同学提起过，倒是试除法之后的筛法，让人耳目一新，值得学习一下。

筛法叙述起来是这样的：首先，2是公认最小的质数，所以，先把所有2的倍数去掉；然后剩下的那些大于2的数里面，最小的是3，所以3也是质数；然后把所有3的倍数都去掉，剩下的那些大于3的数里面，最小的是5，所以5也是质数......上述过程不断重复，直到所求出的质数大于N的开方，这时就已经把某个范围内的合数全都除去（就像被筛子筛掉一样），剩下的就是质数了。

http://coolshell.cn/articles/3738.html把两种算法表达的比较好。