求1～N之间的所有质数
1、试除法：
要判断x是否为质数，主要看是否x能被另外一个质数整除
1）最直接的办法是从2～x-1看是否能整除x
2）x如果有（除自身外）的质因数，那肯定小于等于x/2，所以从2~x/2即可
3）除了2以外，x所有可能的质因数都是奇数，所以先尝试2，然后从3～x/2的所有奇数
4）由于因数是成对出现的。比如，100的因数有：1和100，2和50，4和25，5和20，10和10。其中一个必然小于等于100的开平方，另一个大于等于100的开平方。上限可以缩小至√x。因此先尝试2，然后再针对3到√x的所有奇数。
5）尝试从3到√x 的所有奇数，还是有些浪费。比如要判断101是否质数，101的根号取整后是10，那么，按照境界4，需要尝试的奇数分别是：3，5，7，9。但是你发现没有，对9的尝试是多余的。不能被3整除，必然不能被9整除。其实，只要尝试小于√x
的质数即可。而这些质数，恰好前面已经算出来了。所以可以把已经算出的质数，先保存起来，然后用于后续的试除，效率就大大提高了。
2、筛选法
首先，2是最小的质数，所以先把所有2的倍数去掉；然后剩下的那些大于2的数里面，最小的是3，所以3也是质数；然后把所有3的倍数都去掉，剩下的那些大于3的数里面，最小的是5，所以5也是质数...
上述过程不断重复，就可以把某个范围内的合数全都除去（就像被筛子筛掉一样），剩下的就是质数了。维基百科上有一张很形象的动画，能直观地体现出筛法的工作过程。
如何确定质数的分布范围
判断某个范围内的质数大概有几个，需要用到素数定理。而素数定理，说白了就是数学家找到了一些公式，用来估计某个范围内的素数，大概有几个。在这些公式中，最简洁的就是x/ln(x)。假设要估计1,000,000以内有多少质数，用该公式算出是72,382个，而实际有78,498个，误差约8个百分点。该公式的特点是：估算的范围越大，偏差率越小。
有了素数定理，就可以根据要输出的质数个数，反推出这些质数分布在多大的范围内。因为这个质数分布公式有一定的误差（通常小于15%）。为了保险起见，把反推出的素数分布范围再稍微扩大15%，应该就足够了。
参考http://blog.csdn.net/program_think/article/details/7032600