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