如何判斷素數(shù)？

題目要求：輸出100-200的素數(shù)

首先我們要知道什么是素數(shù)（質(zhì)數(shù)），以防有人忘記（比如剛學(xué)開始學(xué)c的我就忘記了）

素數(shù)（質(zhì)數(shù)）只能被1和它自己整除

7只能被1和7整除，是素數(shù)

9能被3整除，不是素數(shù)

方法1—試除法

這個代碼比較死，只是輸出了100到200之間的素數(shù)，完成了題目的要求

我們可以把它改造成輸入一個數(shù)字，判斷是否是素數(shù)的形式

代碼改造1-1

用戶輸入一個數(shù)字

代碼判斷是否為素數(shù)

是，輸出“是素數(shù)”以及用戶輸入的值

不是，輸出“不是素數(shù)”

結(jié)果如下：

上面的這串代碼能很好地完成我們的需求，但它還有優(yōu)化的空間

方法2—開平方法

方法1中的for循環(huán)為j<i

如果數(shù)字很大的話，要循環(huán)非常多次才能出現(xiàn)j==i的情況

這就拖慢了我們程序運行的速度

這里我們引入一個概念

若i=a*b

a和b中至少有一個數(shù)字 <= 開平方i

如16=2x8=4x4

其中2<4

這樣就能得到一個結(jié)論：

在根號i之前一定有一個數(shù)字n是非素數(shù)的除數(shù)

如果找不到這個數(shù)字n，說明該數(shù)字為質(zhì)數(shù)

利用開平方法，我們可以將需要查找的數(shù)字范圍縮小很多

以下是用該方法完成開頭題目要求的代碼示例：

將這個代碼改造成1-1那種形式也不難，自己試試吧！

感謝你看到最后！希望能夠幫到你~

-----------------------------------

為了幫助大家，輕松，高效學(xué)習(xí)C語言/C++,給大家分享我收集的資源，從最零基礎(chǔ)開始的,幫助大家在學(xué)習(xí)C語言的道路上披荊斬棘！

微信公眾號：C語言編程學(xué)習(xí)基地

C語言零基礎(chǔ)入門教程（83集全）

整理分享（多年學(xué)習(xí)的源碼、項目實戰(zhàn)視頻、項目筆記，基礎(chǔ)入門教程）最重要的是你可以在群里面交流提問編程問題哦！

編程學(xué)習(xí)書籍分享：

編程粉絲交流：