定義：

素數(shù)（Prime number，又稱質(zhì)數(shù)），指在大于1的自然數(shù)中，除了1和該數(shù)自身外，無法被其他自然數(shù)整除的數(shù)

思路一：試除法

1.如果數(shù)字 i 能被 2 ~ i-1 整除，說明 i 就是素數(shù)

代碼（V1）：

#include<stdio.h>
int main()
{int i = 0;//統(tǒng)計素數(shù)個數(shù)int count = 0;for (i = 100; i <= 200; i++){//flag為1表示是素數(shù)int flag = 1;int j = 0;//產(chǎn)生2~i-1的整數(shù)for (j = 2; j < i; j++){if (i % j == 0){flag = 0;}}if (flag == 1){printf("%d ", i);count++;}}printf("\ncount=%d\n", count);return 0;
}

2.上述代碼可進(jìn)行優(yōu)化，我們試除的范圍是2 ~ i-1，但實際上從 i/2 ~ i-1之間的數(shù)是多余的，因為如果一個數(shù)不能被3整除，那么它一定不能被6整除，優(yōu)化后的范圍為[i/2,i-1]，工作量減小一半

代碼（V2）：

include<stdio.h>
int main()
{int i = 0;//統(tǒng)計素數(shù)個數(shù)int count = 0;for (i = 100; i <= 200; i++){//flag為1表示是素數(shù)int flag = 1;int j = 0;//產(chǎn)生2~i/2的整數(shù)for (j = 2; j <= i/2; j++){if (i % j == 0){flag = 0;}}if (flag == 1){printf("%d ", i);count++;}}printf("\ncount=%d\n", count);return 0;
}

3.繼續(xù)進(jìn)行優(yōu)化，如果數(shù)字 i 可以寫成 i = a × b，那么說明a和中至少有一個數(shù)字是<= 開平方 i 的，若能在 2 ~ 開平方i 之間有一個數(shù)能整除i，那么說明后面也有一個數(shù)能整除i，否則就說明后面也不可能有一個數(shù)能整除i

代碼（V3）：

#include<stdio.h>
#include<math.h>
int main()
{int i = 0;//統(tǒng)計素數(shù)個數(shù)int count = 0;for (i = 100; i <= 200; i++){//flag為1表示是素數(shù)int flag = 1;int j = 0;//產(chǎn)生2~開平方i的整數(shù)for (j = 2; j <= sqrt(i); j++){if (i % j == 0){flag = 0;}}if (flag == 1){printf("%d ", i);count++;}}printf("\ncount=%d\n", count);return 0;
}

4.在上述優(yōu)化基礎(chǔ)上，我們知道偶數(shù)不可能是素數(shù)，因此還可以優(yōu)化

代碼（V4）：

#include<stdio.h>
#include<math.h>
int main()
{int i = 0;//統(tǒng)計素數(shù)個數(shù)int count = 0;//只統(tǒng)計范圍內(nèi)奇數(shù)中素數(shù)個數(shù)for (i = 101; i <= 200; i+=2){//flag為1表示是素數(shù)int flag = 1;int j = 0;//產(chǎn)生2~開平方i的整數(shù)for (j = 2; j <= sqrt(i); j++){if (i % j == 0){flag = 0;}}if (flag == 1){printf("%d ", i);count++;}}printf("\ncount=%d\n", count);return 0;
}

運行結(jié)果：

?

思路二：篩法

最小的素數(shù)是2，我們先去除所有能被2整除的數(shù)，此時素數(shù)是3，去掉所有能被3整除的數(shù)，以此類推，如思路一v3所述，只需要在數(shù)組元素的值小于等于所求的最大范圍i的開平方時進(jìn)行此操作即可，去掉所有小于等于開平方i的所有數(shù)的倍數(shù)，剩下的數(shù)就是素數(shù)

?代碼：

#include<stdio.h>
#include<math.h>
int main()
{int i = 0;int arr[200] = { 0 };//統(tǒng)計素數(shù)個數(shù)int count = 0;//將2~200的數(shù)放入數(shù)組中for (i = 0; i < 200; i++){arr[i] = i + 2;}int j = 0;//當(dāng)數(shù)組元素小于開平方i才進(jìn)入循環(huán)while (arr[j] <= sqrt(200)){//遍歷數(shù)組元素，數(shù)組首元素為素數(shù)2，下標(biāo)為0，作為除數(shù)//那么首個被除數(shù)應(yīng)該從下標(biāo)為1的數(shù)3開始向后遍歷for (i = j + 1; i < 200; i++){//將能被素數(shù)整除的數(shù)組元素置為0if (arr[i] % arr[j] == 0){arr[i] = 0;}}j++;//此時被置為0的數(shù)都不是素數(shù)，無需判斷while (arr[j] == 0){j++;}}for (i = 98; i < 200; i++){//在上述操作執(zhí)行結(jié)束后，只有尚未被置0的數(shù)才是素數(shù)if (arr[i] != 0){count++;printf("%d ", arr[i]);}}printf("\ncount=%d\n", count);return 0;
}

運行結(jié)果：

?