埃拉托斯特尼篩法
質數又稱素數。指在一個大于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，一些文章的備份和平常做的一些項目會存放在這裡。