埃拉托斯特尼筛法
质数又称素数。指在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。怎么判断n以内的哪些数是质数呢？
厄拉多塞是一位古希腊数学家，他在寻找素数时，采用了一种与众不同的方法：先将2－N的各数放入表中，然后在2的上面画一个圆圈，然后划去2的其他倍数；第一个既未画圈又没有被划去的数是3，将它画圈，再划去3的其他倍数；现在既未画圈又没有被划去的第一个数是5，将它画圈，并划去5的其他倍数……依次类推，一直到所有小于或等于N的各数都画了圈或划去为止。这时，表中画了圈的以及未划去的那些数正好就是小于 N的素数。
如下图所示：
而其实迭代系数i不需要遍历到n-1为止，只需到√(n-1)即可。反证法：
- 如果n-1不是质数，那么n-1可以化解成两个整数因子相乘，n-1=d1×d2。
- 如果d1和d2均大于√(n-1)，则有：n-1＝d1×d2 > √(n-1)×√(n-1)＝n-1
- 则n-1必有因子d1或d2小于等于√(n-1)，从而n-1可以被小于或等于√(n-1)的某整数的遍历到。
- 小于n-1的整数如果是质数必然会被遍历到。
如果N是合数，则一定存在大于1小于N的整数d1和d2，使得N=d1×d2。如果d1和d2均大于√N，则有：N＝d1×d2>√N×√N＝N。而这是不可能的，所以，d1和d2中必有一个小于或等于√N。
代码如下：
1 public class Solution {
2 public int countPrimes(int n) {
3 if(n <= 2)
4 return 0;
5 boolean[] prime = new boolean[n];
6 for(int i =2; i < n; ++i) {
7 prime[i] = true;
8 }
9 for(int i = 2; i <= Math.sqrt(n-1); ++i) { //i <= √(n-1) 即可
10 if(prime[i]) {
11 for(int j = i + i;j < n; j += i) {
12 prime[j] = false;
13 }
14 }
15 }
16 int count = 0;
17 for(int i = 2; i < n; ++i) {
18 if(prime[i])
19 count++;
20 }
21 return count;
22 }
23 } 其他方法
任何一个自然数，总可以表示成为如下的形式之一：
6N，6N+1，6N+2，6N+3，6N+4，6N+5 (N=0，1，2，…)
N>1时，其中6N，6N+2，6N+3，6N+4必然不是质数，只可能是6N+1或者6N+5，即6N±1。因此可以通过6N±1筛子大量筛减非质数。
作 者：Angel_Kitty
出 处：https://www.cnblogs.com/ECJTUACM-873284962/
关于作者：阿里云ACE，目前主要研究方向是Web安全漏洞以及反序列化。如有问题或建议，请多多赐教！
版权声明：本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文链接。
特此声明：所有评论和私信都会在第一时间回复。也欢迎园子的大大们指正错误，共同进步。或者直接私信我
声援博主：如果您觉得文章对您有帮助，可以点击文章右下角【推荐】一下。您的鼓励是作者坚持原创和持续写作的最大动力！
欢迎大家关注我的微信公众号IT老实人(IThonest)，如果您觉得文章对您有很大的帮助，您可以考虑赏博主一杯咖啡以资鼓励，您的肯定将是我最大的动力。thx.
我的公众号是IT老实人(IThonest)，一个有故事的公众号，欢迎大家来这里讨论，共同进步，不断学习才能不断进步。扫下面的二维码或者收藏下面的二维码关注吧(长按下面的二维码图片、并选择识别图中的二维码)，个人QQ和微信的二维码也已给出，扫描下面👇的二维码一起来讨论吧！！！
欢迎大家关注我的Github，一些文章的备份和平常做的一些项目会存放在这里。