零、前言?
??簡介：大家好,我是小虛竹。Java領域優質創，CSDN博客可能，華為云享可能，掘金年度人氣，阿里云可能博主，51CTO可能博主
??技術活，該賞
??點贊 收藏 ?再看，養成習慣
?
今天是學習 「JAVA語言」 打卡得第2天，我得學習策略很簡單，題海策略+ 費曼學習法。如果能把這100題都認認真真自己實現一遍，那意味著 「JAVA語言」 已經筑基成功了。后面得進階學習，可以繼續跟著我，一起走向架構師之路。
一、題目描述題目：判斷 101-200 之間有多少個素數，并輸出所有素數。
二、解題思路：循環法素數，又稱質數，定義是：除了1和它本身以外不再有其他得除數整除。
判斷素數得方法：從2到n-1判斷有沒有能整除n得數。如果有，則不是素數，否則，是素數
三、代碼詳解public class Basics02 { public static void main(String[] args) { int i, j; // 從101～200進行篩選 for (i = 101; i <= 200; i++) { // 從2～i-1得值 for (j = 2; j <= i - 1; j++) { if (i % j == 0){ // i與j互相取余，如果余數為0則肯定不是素數，跳出循環 break; } } if (i == j) { // 如果i等于j則說明完成了從2～i-1得循環，說明每一次取余得值都不是0。結果肯定是素數 System.out.println(i + "是素數"); } } }}解法二：循環對半法思路
素數，又稱質數，定義是：除了1和它本身以外不再有其他得除數整除。 從2到n-1判斷有沒有能整除n得數。每拿到一個數，判斷該數是否是素數；
從2開始，遍歷到該數得一半得數據，看是否有數據可以整除它，有就不是素數，沒有就是素數。
注：為什么是該數得一半，因為素數得特性，那肯定不能被2整除了，被2后面得數整除得到得數據肯定小于該數得一半。
這種寫法會少循環一半得數據。提高效率。
代碼詳解public class Basics02_2 { public static void main(String[] args) { int i, j; // 從101～200進行篩選 for (i = 101; i <= 200; i++) { //標記位 //當前得數是素數 boolean flag = true; // 從2～i-1得值 for (j = 2; j <= i /2; j++) { if (i % j == 0){ // i與j互相取余，如果余數為0則肯定不是素數，跳出循環 flag = false; break; } } if (flag) { // 根據標記位flag得結果。true結果肯定是素數 System.out.println(i + "是素數"); } } }}解法三：開方法思路
素數，又稱質數，定義是：除了1和它本身以外不再有其他得除數整除。 開方求解 原理：一個數得約數在其開方得左邊，那肯定會存在一個約數在其開方得右邊，所以只要循環到開方數就行。 證明： 假設數m=p*q,且p≤q 則m≥p*p 所以p<=√m
由此可得出上面得結論，一個數如果存在約數，那肯定一個約數在其開方得左邊，另一個約數在其開方得右邊。
代碼詳解public class Basics02_3 { public static void main(String[] args) { // 從101～200進行篩選 for (int i = 101; i <= 200; i++) { //開方求解 原理：一個數得約數在其開方得左邊，那肯定會存在一個約數在其開方得右邊，所以只要循環到開方數就行 int sqrtNum = (int)Math.sqrt(i); for (int k = 2; k <= sqrtNum; k++) { if (i % k == 0){ // i與k互相取余，如果余數為0則肯定不是素數，跳出循環 break; } //執行到這里，說明這個數在其開方得左邊找不到約數 if(k>= sqrtNum){ System.out.println(i + "是素數"); } } } }}解法四：試除法升級版思路
其實前面幾種都是試除法，那虛竹哥就簡單介紹下試除法得概念： "試除"，顧名思義，就是不斷地嘗試能否整除。比如要判斷自然數 x 是否素數，就不斷嘗試小于 x 且大于1得自然數，只要有一個能整除，則 x 是合數；否則，x 是素數。
素數，又稱質數，定義是：除了1和它本身以外不再有其他得除數整除。 開方求解 原理：一個數得約數在其開方得左邊，那肯定會存在一個約數在其開方得右邊，所以只要循環到開方數就行。 質因數，是指能整除給定正整數得質數。指一個正整數得約數，并且該數還屬于是質數得數字。 判斷素數，真得需要拿2~ 間得所有整數去除么？這樣有些浪費，比如要判斷101是否質數，101得根號取整后是10，需要嘗試得數分別是：3，4，5，6，7，8，9，10得數。 明顯我們知道，除了2之外，所有得可能得質因數，都是奇數。那再優化下，就是需要嘗試得數分別是：3，5，7，9得數。其中9肯定不行。那就是3，5，7。。 重點來了，有沒有發現什么，都是素數啊。 結論：只要嘗試試除小于得素數即可。 代碼實現步驟：
public class Basics02_4 { public static void main(String[] args) { //從101～200進行篩選 循環 //只要嘗試小于√x 得質數即可 //獲取√x 得質數 for (int i = 101; i <= 200; i++) { //√x得值 int sqrtNum = (int)Math.sqrt(i); //只要嘗試小于√x 得質數即可 //√x 得質數得獲取 List<Integer> primeList = primes(2,sqrtNum); boolean flag = true; for (int j = 0; j < primeList.size(); j++) { if (i % primeList.get(j) == 0){ // i與k互相取余，如果余數為0則肯定不是素數，跳出循環 flag = false; break; } } if(flag){ System.out.println(i + "是素數"); } } } private static List<Integer> primes(int startNum,int endNum){ List<Integer> primeList = new ArrayList<>(); primeList.add(2); primeList.add(3); for (int i = startNum; i <= endNum; i++) { //開方求解 原理：一個數得約數在其開方得左邊，那肯定會存在一個約數在其開方得右邊，所以只要循環到開方數就行 int sqrtNum = (int)Math.sqrt(i); for (int k = 2; k <= sqrtNum; k++) { if (i % k == 0){ // i與k互相取余，如果余數為0則肯定不是素數，跳出循環 break; } //執行到這里，說明這個數在其開方得左邊找不到約數 if(k>= sqrtNum){ primeList.add(i); } } } return primeList; }}解法五：素數篩思路
素數得倍數不是素數.
代碼詳解public class Basics02_5 { public static void main(String[] args) { //定義vis數組 true： 表示不是素數 false：表示是素數 boolean[] vis = new boolean[201];//默認初始值為false，即默認全為素數 vis[0] = vis[1] = true; //0,1 不是素數 for (int i = 2; i <= 200; i++) { //素數得倍數一定不是素數 for (int j = i*i; j <= 200; j += i) { vis[j] = true; } } for (int i = 0; i <= 200; i++) { if(!vis[i] && i>101){ System.out.println(i + "是素數"); } } }}
我是虛竹哥，我們下一題見～
