定義：

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

思路一：試除法

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

代碼（V1）：

#include<stdio.h>
int main()
{
	int i = 0;
	//統(tǒng)計(jì)素?cái)?shù)個數(shù)
	int count = 0;
	for (i = 100; i <= 200; i++)
	{
		//flag為1表示是素?cái)?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，但實(shí)際上從 i/2 ~ i-1之間的數(shù)是多余的，因?yàn)槿绻粋€數(shù)不能被3整除，那么它一定不能被6整除，優(yōu)化后的范圍為[i/2,i-1]，工作量減小一半

代碼（V2）：

include<stdio.h>
int main()
{
	int i = 0;
	//統(tǒng)計(jì)素?cái)?shù)個數(shù)
	int count = 0;
	for (i = 100; i <= 200; i++)
	{
		//flag為1表示是素?cái)?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)計(jì)素?cái)?shù)個數(shù)
	int count = 0;
	for (i = 100; i <= 200; i++)
	{
		//flag為1表示是素?cái)?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ù)不可能是素?cái)?shù)，因此還可以優(yōu)化

代碼（V4）：

#include<stdio.h>
#include<math.h>
int main()
{
	int i = 0;
	//統(tǒng)計(jì)素?cái)?shù)個數(shù)
	int count = 0;
	//只統(tǒng)計(jì)范圍內(nèi)奇數(shù)中素?cái)?shù)個數(shù)
	for (i = 101; i <= 200; i+=2)
	{
		//flag為1表示是素?cái)?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;
}

運(yùn)行結(jié)果：

?文章來源地址http://www.zghlxwxcb.cn/news/detail-511577.html

思路二：篩法

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

?代碼：

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

運(yùn)行結(jié)果：

?

到了這里，關(guān)于C語言 - 判斷素?cái)?shù)的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！