質(zhì)數(shù)篩（樸素、埃氏、歐拉）

介紹

作為和數(shù)學(xué)高度結(jié)合的一門(mén)學(xué)科，程序設(shè)計(jì)中經(jīng)常會(huì)用到數(shù)學(xué)上的性質(zhì)和概念，或者說(shuō)，計(jì)算機(jī)一開(kāi)始就是為了解決數(shù)學(xué)問(wèn)題而發(fā)明的。在做題的過(guò)程中，我們經(jīng)常遇到質(zhì)數(shù)相關(guān)的題目，那么，我們?nèi)绾闻袛嘁粋€(gè)數(shù)是不是質(zhì)數(shù)呢？如何把質(zhì)數(shù)全部打入表中呢？今天，我將介紹三種常見(jiàn)的篩取質(zhì)數(shù)的方法。

---

樸素篩

代碼實(shí)現(xiàn)

int main()
{
	int n, c, N = 0, prime[10000];//質(zhì)數(shù)數(shù)組
	scanf("%d", &n);
	for (int i = 2; i <= n; i++)//檢測(cè)i是否為質(zhì)數(shù)
	{
		c = 1;
		for (int j = 2; j * j <= i + 1; j++)//測(cè)試i是否能被j整除
			if (i % j == 0 && i != 2)
			{
				c = 0;
				break;
			}
		if(c) prime[N++] = i;//填入并計(jì)數(shù)
	}
	for (int i = 0; i < N; i++) printf("%d ", prime[i]);
	return 0;
}

分析

根據(jù)質(zhì)數(shù)的定義，質(zhì)數(shù)有且只有兩個(gè)因數(shù)，即1和它本身。

樸素篩就根據(jù)這最基本的性質(zhì)，從2開(kāi)始遍歷，直到它的平方根，依次取余，如果整除了就違反了質(zhì)數(shù)有且只有兩個(gè)因數(shù)的性質(zhì)，可以將其排除。

之所以只需要遍歷到平方根，是因?yàn)檎龝r(shí)，結(jié)果也是它的一個(gè)因數(shù)，故只需要遍歷到平方根，便可以將所有可能是因數(shù)的數(shù)試到。

for (int i = 2; i <= n; i++)//檢測(cè)i是否為質(zhì)數(shù)
	{
		c = 1;
		for (int j = 2; j * j <= i; j++)//測(cè)試i是否能被j整除
			if (i % j == 0 && i != 2)
			{
				c = 0;
				break;
			}
		if(c) prime[N++] = i;//填入并計(jì)數(shù)
	}

這里是樸素篩的核心部分。

值得注意的是，for循環(huán)的跳出條件設(shè)置為j*j<=i，避免了sqrt函數(shù)的使用，可以顯著提升運(yùn)行速度。

而變量c的設(shè)置則是為了標(biāo)識(shí)i是否是質(zhì)數(shù)，若是因?yàn)榕袛酁楹蠑?shù)而跳出，則將c賦為0，后續(xù)不做處理，反之，將其存入數(shù)組。

補(bǔ)充

整個(gè)算法的時(shí)間復(fù)雜度為O(nlogn)。很顯然，這個(gè)算法是最基礎(chǔ)的暴力遍歷，如果題目給的數(shù)據(jù)大一點(diǎn)就會(huì)被T得很慘，比賽時(shí)間充裕的情況盡量不要用樸素篩，就跟盡量用快排別用冒泡一個(gè)道理。

---

埃氏篩

代碼實(shí)現(xiàn)

#include<stdio.h>
#include<stdbool.h>
#define maxNum 1000000001//定義最大值
bool priNum[maxNum];//質(zhì)數(shù)為真，否則為假
void savePriNum()//創(chuàng)建預(yù)處理質(zhì)數(shù)集
{
	for (int i = 0; i < maxNum; i++)
		priNum[i] = true;//默認(rèn)真
	priNum[0] =priNum[1] = false;
	for (int i = 2; i * i < maxNum ; i++)//依次篩掉i的倍數(shù)，不包括i
		for (int j = 2 * i; j < maxNum; j += i)
            priNum[j] = false;
}

int main()
{
	savePriNum();
	int n;
	scanf("%d", &n);
	for (int i = 2; i <= n; i++)
		if (priNum[i])
            printf("%d\n", i);
	return 0;
}

分析

質(zhì)數(shù)有且只有兩個(gè)因數(shù)，那也就是說(shuō)，任何數(shù)的倍數(shù)都不可能是質(zhì)數(shù)，那我們只需要在遍歷2到它的平方根，并標(biāo)記這些數(shù)在要求范圍內(nèi)的倍數(shù)為合數(shù)，那剩下的數(shù)就是質(zhì)數(shù)了。

#include<stdbool.h>
#define maxNum 1000000001//定義最大值
bool priNum[maxNum];//質(zhì)數(shù)為真，否則為假

首先，我們先創(chuàng)建一個(gè)布爾型數(shù)組來(lái)存放質(zhì)數(shù)。因?yàn)閿?shù)據(jù)范圍極大，而我們只需要存放0和1來(lái)標(biāo)記質(zhì)數(shù)合數(shù)，所以我們采用值只有true和false的布爾型變量，來(lái)節(jié)省空間。

void savePriNum()//創(chuàng)建預(yù)處理質(zhì)數(shù)集
{
	for (int i = 0; i < maxNum; i++)
		priNum[i] = true;//默認(rèn)真
	priNum[0] =priNum[1] = false;
	for (int i = 2; i * i < maxNum ; i++)//依次篩掉i的倍數(shù)，不包括i
		for (int j = 2 * i; j < maxNum; j += i)
            priNum[j] = false;
}

我們將存表操作封裝進(jìn)函數(shù)中。

首先，我們默認(rèn)每個(gè)數(shù)都為質(zhì)數(shù)，接著，特判0和1不是質(zhì)數(shù)，同時(shí)，0和1也不在我們遍歷的過(guò)程中。

我們從2開(kāi)始，遍歷到范圍最大值的平方根，標(biāo)記這些數(shù)在要求范圍內(nèi)的倍數(shù)為合數(shù)。

這樣，我們想判斷x是不是質(zhì)數(shù)，只需要查詢(xún)priNum[x]的值就可以了。

補(bǔ)充

整個(gè)算法的時(shí)間復(fù)雜度為O(nloglogn)，已經(jīng)很逼近線(xiàn)性時(shí)間O(n)了，但是我們可以發(fā)現(xiàn)，埃氏篩在標(biāo)記合數(shù)時(shí)，是有重復(fù)標(biāo)記的。當(dāng)一個(gè)合數(shù)擁有多個(gè)因數(shù)時(shí)，就會(huì)被標(biāo)記多次，例如12擁有因數(shù)1，2，3，4，6，12，除去1和12，在遍歷2，3，4，6時(shí)，12都被標(biāo)記了一次，所以，埃氏篩還并不是線(xiàn)性時(shí)間。

---

歐拉篩

代碼實(shí)現(xiàn)

#include<stdio.h>
#include<stdbool.h>
#define maxNum 1000000001//定義最大值
bool priNum[maxNum];//質(zhì)數(shù)為真，否則為假
int  pri[maxNum], N = 0;
void savePriNum()//創(chuàng)建預(yù)處理質(zhì)數(shù)集
{
	for (int i = 0; i < maxNum; i++)
		priNum[i] = true;//全部填入真
	priNum[0] = priNum[1] = false;
	for (int i = 2; i * i <= maxNum; i++)
		if (priNum[i])
		{
			pri[N] = i;//存入數(shù)組并計(jì)數(shù)
			N++;
			for (int j = 0; j < N; j++)//若i為質(zhì)數(shù)，則標(biāo)記它和其他質(zhì)數(shù)的每一個(gè)乘積
				if (pri[j] * i < maxNum) priNum[pri[j] * i] = false;
				else break;//
		}
		else
			for (int j = 0; j < N; j++)
			{
				if (pri[j] * i < maxNum) priNum[pri[j] * i] = false;//若i為合數(shù)，則標(biāo)記它和其他質(zhì)數(shù)的乘積
				if (i % pri[j] == 0) break;//直到i整除到某質(zhì)數(shù)
			}
	return 0;
}

int main()
{
	savePriNum();
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		if (priNum[i])
			printf("%d ", i);
	return 0;
}

分析

歐拉篩又稱(chēng)線(xiàn)性篩，在歐拉篩中每個(gè)合數(shù)都只會(huì)被標(biāo)記一次，因此，算法的時(shí)間是線(xiàn)性的，時(shí)間復(fù)雜度到了O(n)。

為了實(shí)現(xiàn)每個(gè)合數(shù)只被標(biāo)記一次，在歐拉篩中我們規(guī)定每個(gè)合數(shù)都只會(huì)被它的最小因數(shù)標(biāo)記，這里的意思是通過(guò)該數(shù)最小因數(shù)*某數(shù)=該數(shù)來(lái)標(biāo)記該數(shù)。

#include<stdio.h>
#include<stdbool.h>
#define maxNum 1000000001//定義最大值
bool priNum[maxNum];//質(zhì)數(shù)為真，否則為假
int  pri[maxNum], N = 0;

預(yù)處理時(shí)，我們另外創(chuàng)建一個(gè)數(shù)組，用于即時(shí)存放篩選出的質(zhì)數(shù)，同時(shí)設(shè)置變量N用于記錄當(dāng)前質(zhì)數(shù)數(shù)量。

void savePriNum()//創(chuàng)建預(yù)處理質(zhì)數(shù)集
{
	for (int i = 0; i < maxNum; i++)
		priNum[i] = true;//全部填入真
	priNum[0] = priNum[1] = false;
	for (int i = 2; i * i <= maxNum; i++)
		;//......
	return 0;
}

我們同樣將存表操作封裝進(jìn)函數(shù)中，默認(rèn)存真，特判01，同樣的遍歷至平方根，不做贅述。

if (priNum[i])
	{
		pri[N] = i;//存入數(shù)組并計(jì)數(shù)
		N++;
		for (int j = 0; j < N; j++)//若i為質(zhì)數(shù)，則標(biāo)記它和其他質(zhì)數(shù)的每一個(gè)乘積
			if (pri[j] * i < maxNum) priNum[pri[j] * i] = false;
			else break;//
	}

當(dāng)我們遍歷到一個(gè)質(zhì)數(shù)時(shí)，我們將其存入質(zhì)數(shù)數(shù)組并計(jì)數(shù)，然后將其與已經(jīng)存入的質(zhì)數(shù)相乘，并標(biāo)記相乘的積為合數(shù)。

兩個(gè)不同質(zhì)數(shù)相乘的積有且只有4個(gè)因數(shù)，兩個(gè)相同質(zhì)數(shù)相乘的積有且只有3個(gè)因數(shù)，這是分解質(zhì)因數(shù)的原理。

也因此，我們通過(guò)此法標(biāo)記的數(shù)，必然是通過(guò)它的最小因數(shù)來(lái)標(biāo)記的。

else
	for (int j = 0; j < N; j++)
	{
		if (pri[j] * i < maxNum) priNum[pri[j] * i] = false;//若i為合數(shù)，則標(biāo)記它和其他質(zhì)數(shù)的乘積
		if (i % pri[j] == 0) break;//直到i整除到某質(zhì)數(shù)
	}

而當(dāng)我們遍歷到一個(gè)合數(shù)時(shí)，我們同樣將其與已經(jīng)存入的質(zhì)數(shù)相乘，并標(biāo)記相乘的積為合數(shù)。

但歐拉篩的精髓之處來(lái)了。

當(dāng)該數(shù)在相乘中遍歷到自己的一個(gè)因數(shù)后，就需要break跳出，終止循環(huán)。

同樣以12舉例，當(dāng)i遍歷到4，j遍歷到2時(shí)，4%2==0，此時(shí)需要跳出，j不能繼續(xù)遍歷到3，若通過(guò)4*3=12來(lái)標(biāo)記12，在i遍歷到6時(shí)，6*2=12便會(huì)重復(fù)遍歷，也違反了合數(shù)需要被自己的最小因子標(biāo)記的規(guī)則。

---

總結(jié)

樸素篩和埃氏篩的實(shí)現(xiàn)原理是比較簡(jiǎn)單的，使用的場(chǎng)景也比較廣泛，但在個(gè)別的競(jìng)賽題中會(huì)T，必須使用歐拉篩。

歐拉篩理解的過(guò)程是有點(diǎn)難的，但在真正理解之后思路會(huì)非常清晰，主要就是合數(shù)需要被自己的最小因子標(biāo)記的規(guī)則，需要細(xì)細(xì)體會(huì)。

以上便是質(zhì)數(shù)篩三種篩法的介紹，本文由涼茶coltea撰寫(xiě)，轉(zhuǎn)載請(qǐng)注明出處。

總結(jié)

以上是生活随笔為你收集整理的质数筛（朴素、埃氏、欧拉）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。