對於判斷一個正整數是否為質數的深入與思考

含有兩個因數的數一定是質數對嗎

需求

今天在學習的過程中，遇到一個這樣的一個題目，需求是這樣的：

從控制檯接收一個正整數，判斷該質數是否為質數？

質數的概念：質數是指在大於1的自然數中，除了1和它本身以外不再有其他因數的自然數。

那什麼是因數呢？就比如6=2*3，6=1*6，那麼6的因數是1、2、3、6，除了1和6之外，還有2和3兩個因數，所以6不是質數，而5只有1和5本身兩個因數，所以5是因數。

那麼該如何用Java程式碼實現呢？

Java程式碼

初步思考：從鍵盤獲取資料後，先判斷接收到的資料是否為正整數，然後進行for迴圈結合if和else if語句進行判斷。

判斷思路是這樣的，使用變數num統計次數，如果num等於1，說明該數就是1，不是質數，也不是合數，如果num等於2，說明只有1和其自身兩個因數，則n就是質數，除此之外，是合數。

程式碼如下：

Java程式碼

文字程式碼如下：

public class Test04{//定義一個Test04類

public static void main（String［］ args）{

java。util。Scanner scan = new java。util。Scanner（System。in）；

//接收資料

int n = scan。nextInt（）；

判斷輸入的n是否為正整數

if（n <= 0）{

System。out。println（“輸入的數字有誤”）；

}else{//n為正整數

int num = 0；//num統計次數，初始化為0

for（int i = 1； i <= n； i++）{

if（n % i == 0）{//判斷條件，取餘為零

num ++；//統計次數

}

}

if（num == 1）{//次數為1，說明在for迴圈中只執行一次，即n為1，不是質數也不是合數；

System。out。println（n + “既不是質數，也不是合數”）；

}else if（num == 2）{//說明在for迴圈中，n只有1和其自身兩個因數

System。out。println（n + “是質數”）；

}else{//num次數大於2，說明除了1和自身之外，還有其他因數

System。out。println（n + “是合數”）；

}

}

}

在我編寫完畢後，程式碼執行結果正確，但是我又在思考，該程式碼的執行是複雜，時間複雜度是不是過大，其執行次數過多，該程式碼能不能進行最佳化呢？

程式碼最佳化

在老師的提醒下，可以使用

break語句以及三目運算子

來進行對程式碼進行編寫，最終發現其程式碼更簡潔。

public class Test05{

public static void main（String［］ args）{

// 從控制檯接收一個正整數。

java。util。Scanner s = new java。util。Scanner（System。in）；

int num = s。nextInt（）；

//考慮在外邊準備一個布林型別的標記。

boolean zhiShu = true； // true表示是質數。

for（int i = 2； i < num； i++）{

if（num % i == 0）{

/**

假設輸入的是7：

7 / 1 不用判斷

7 / 2 需要判斷

7 / 3 需要判斷

7 / 4 需要判斷（假設這個判斷，發現可以整除，就沒必要往下判斷了。）

7 / 5 需要判斷

7 / 6 需要判斷

7 / 7 不用判斷

*/

// 迴圈沒必要執行了，為了效率，這裡要終止迴圈

zhiShu = false；

break；

}

}

System。out。println（num + （zhiShu ？ “是” ： “不是”） + “質數”）；

}

結論

對於質數的判斷，我想，應該還有很多方法，或許還有很多更加簡便的方法來判斷，從中獲得最大的感觸就是，要學會舉一反三，針對不同的需求，學會分析和思考，在初步完成程式碼後，要思考，有沒有更好的改進來最佳化，使其程式碼更少，效率更高。

所以，培養程式設計思維真的挺重要！

半路出家的程式設計師，目前還在自學，更多理解還不是很到位，希望大佬多給出一些中肯的建議以及方法。