可以看到，使用筛法求第n个质数的时间复杂度为O(n)，缺点在需要提前求得筛选的结果，增加了空间复杂度，筛选结果可以用比特位来表示以节省空间。

此外还有一个问题，在求第n个质数的时候，如何要确定第n个质数的大致范围，以确定筛选结果的布尔数组长度。根据素数定理，可以用来估算某个范围内的素数个数，可以用公式x/ln(x)来描述，ln表示自然对数，假设要估计10000以内有多少质数，代入公式10000/ln(10000)得到的结果为1085.73,使用上面的筛法得到的10000以为的质数个数为1229，可以看到估计值比实际值略小一点，估计的范围越大，估计值与实际值的误差越小。实际使用中可以通过公式计算估计值，然后按一定百分比扩大范围即可。

文章转自: http://segmentfault.com/a/1190000004162829