質(zhì)數(shù)就是除了1和它本身外沒有其他因數(shù)

一. 暴力枚舉

假設(shè)現(xiàn)在有一個(gè)數(shù)num，要求我們判斷是否是質(zhì)數(shù)，由定義知我們可以遍歷從2到 num-1的所有數(shù)，假

設(shè)都不能被整除，則num是質(zhì)數(shù)，否則不是，C語言代碼實(shí)現(xiàn)如下。

其中track用來檢測是否遍歷完從2到num-1的所有數(shù)

int main()
{
	int n = 0;
	int track = 0;
	printf("請輸入要判斷的數(shù): ");
	scanf("%d", &n);
	for (int i = 2; i < n; i++)
	{
		if (n % i == 0)
		{
			track = 1;
			break;
		}
	}
	if (track == 1)
		printf("這個(gè)數(shù)不是質(zhì)數(shù)\n");
	else
		printf("這個(gè)數(shù)是質(zhì)數(shù)\n");
	return 0;
}

二. 暴力求解的優(yōu)化版本

實(shí)際上我們只需要遍歷從2到√num的數(shù)就可以了。

因?yàn)閷?duì)于非質(zhì)數(shù)num來說有 a * b = num；其中a和b不可能同時(shí)大于√num，也就是說num是非質(zhì)數(shù)的充要條件是在 [2,num-1]的區(qū)間上有因數(shù),根據(jù)這一點(diǎn)可以對(duì)代碼進(jìn)行優(yōu)化。

int main()
{
	int n = 0;
	int track = 0;
	printf("請輸入要判斷的數(shù): ");
	scanf("%d", &n);
		for (int i = 2; i <= sqrt(n); i++)
		{
			if (n % i == 0)
			{
				track = 1;
				break;
			}
		}
		if (track == 1)
			printf("這個(gè)數(shù)不是質(zhì)數(shù)\n");
		else
			printf("這個(gè)數(shù)是質(zhì)數(shù)\n");
	
	return 0;
}

三.埃拉托斯特尼篩法

如果要求我們判斷的數(shù)字很多，那么上面兩種方法的效率就極其低下，因?yàn)槊颗袛嘁粋€(gè)數(shù)都要從2開始遍歷，計(jì)算機(jī)會(huì)做很多重復(fù)操作。

換一種思路，我們可以選一批質(zhì)數(shù)，質(zhì)數(shù)的倍數(shù)是合數(shù)（非質(zhì)數(shù)），那么就可以把這些合數(shù)篩掉，經(jīng)過多輪篩選后剩下的就全部是質(zhì)數(shù)了。

看了前面的敘述可能有的朋友會(huì)有點(diǎn)懵，我解釋一下。

細(xì)節(jié)部分?

1. 怎樣選一批素?cái)?shù)能將區(qū)間內(nèi)所有合數(shù)都篩完？

從2開始到√n的所有素?cái)?shù)。首先1肯定沒有篩選功能（1的任意倍數(shù)都是其本身）。

對(duì)于√n之后的素?cái)?shù)，比如說用√n + 1進(jìn)行篩選?，得到的可篩選的數(shù)是?[(√n + 1) *? 2, (√n +1) *?√n] 中的整數(shù)，但是這些整數(shù)都有一個(gè)小于等于√n的約數(shù)，因此在我們遍歷前面的數(shù)時(shí)已經(jīng)將他們刪除掉了，所以沒必要重復(fù)，只需要 [2,√n)的所有素?cái)?shù)即可。?

2.篩選過程具體是怎樣的？

不清楚篩選過程的朋友可以看看這張圖，這張圖搬運(yùn) 自公眾號(hào) “coder梁”，做的特別清楚。

3.具體代碼

C語言實(shí)現(xiàn)。

int main()
{
	//埃式篩法
	int n = 0;
	printf("請輸入要判斷的數(shù) ");
	scanf("%d", &n);
	int* prime = (int*)malloc(n * sizeof(int));//定義一個(gè)可以存放n個(gè)數(shù)的數(shù)組
	if (!prime)
	{
		printf("創(chuàng)建數(shù)組失敗\n");
		exit(-1);
	}
	//將prime數(shù)組全部初始化成1，表示全部是素?cái)?shù)
	for (int i = 0; i < n; i++)
	{
		prime[i] = 1;
	}
	//從2開始篩選
	for (int i = 2; i <= sqrt(n); i++)
	{
		if (prime[i - 1])        //如果是質(zhì)數(shù)
		{
			for (int j = i * i; j <= n; j += i) //則將其剔除
				prime[j - 1] = 0;
		}
	}
	//打印
	for (int i = 0; i < n; i++)
	{
		if (prime[i] != 0)
			printf("%d ", i + 1);
	}
	printf("\n");
	return 0;
}

總結(jié)