1.什么是素?cái)?shù)

素?cái)?shù)又稱(chēng)質(zhì)數(shù)。一個(gè)大于1的自然數(shù)，除了1和它自身外，不能被其他自然數(shù)整除的數(shù)叫做素?cái)?shù)；否則稱(chēng)為合數(shù)（規(guī)定1既不是素?cái)?shù)也不是合數(shù)）。

在許多的程序設(shè)計(jì)題目中，都會(huì)涉及到素?cái)?shù)的判斷，那我們?cè)撊绾斡行袛嗨財(cái)?shù)呢？

2.素?cái)?shù)的兩種判斷方法

（1）暴力法

從 2 到 √n

根據(jù)素?cái)?shù)的定義，我們可以使用逐個(gè)試除的方式來(lái)判斷素?cái)?shù)，如果能為要判斷的數(shù)找到一個(gè)除了1和自身以外的因數(shù)，那么它就是合數(shù)；反之，就是素?cái)?shù)。

而這樣的因數(shù)的范圍必然在 2 ~ √n之間，所以我們便可以得到以下代碼。

int isPrime(int n)
{
	if(n <= 1)
	{
		return 0;
	}
	for (int i = 2; i * i <= n; i++)
	{
		if (n % i == 0)
		{
			return 0;
		}
	}
	return 1;
}

該函數(shù)就可以判斷輸入的數(shù)是否為素?cái)?shù)。

這個(gè)范圍還可以更進(jìn)一步地縮小。

6n-1與6n+1

數(shù)學(xué)上有一個(gè)定理，除了2和3外，只有形如6n-1和6n+1的自然數(shù)可能是素?cái)?shù)，這里的n是大于等于1的整數(shù)。

如何理解這個(gè)定理呢？

所有自然數(shù)都可以寫(xiě)成6n,6n+1,6n+2,6n+3,6n+4,6n+5這6種。 那么我們就可以得到下表。

其中6n+5可以寫(xiě)作6n-1，所以除了2和3的素?cái)?shù)必然形如6n-1或6n+1。

于是我們可以寫(xiě)出如下代碼。

int isPrime(int n)
{
	if(n <= 1) return 0;
	else if(n == 2 || n == 3) return 1;
	else if(n % 6 != 1 && n % 6 != 5) return 0;
	for (int i = 5; i * i <= n; i++)
	{
		if (n % i == 0)
		{
			return 0;
		}
	}
	return 1;
}

優(yōu)化后的算法具有更高的效率。

（2）篩法

暴力算法雖然可以判斷某個(gè)數(shù)是否為素?cái)?shù)，但是當(dāng)它面對(duì)大量需要判斷的數(shù)據(jù)時(shí)，它的效率會(huì)顯得十分低下，我們也有更好地方法來(lái)求一定范圍里的素?cái)?shù)，它就是我們的篩法。

篩法，顧名思義，就是將合數(shù)從數(shù)據(jù)中篩除，剩下的自然就都是素?cái)?shù)了。

篩法也分為兩種，讓我們來(lái)逐一介紹。

埃氏篩

埃拉托斯特尼 篩法，簡(jiǎn)稱(chēng) 埃氏篩，是一種由希臘數(shù)學(xué)家埃拉托斯特尼所提出的一種簡(jiǎn)單檢定素?cái)?shù)的算法。

要得到自然數(shù)n以?xún)?nèi)的全部素?cái)?shù)，必須把不大于根號(hào)n的所有素?cái)?shù)的倍數(shù)剔除，剩下的就是素?cái)?shù)。

下面的程序就是通過(guò)埃氏篩判斷 0 ~ MAXSIZE-1是否為素?cái)?shù)。

#define MAXSIZE 10000
int isPrime[MAXSIZE] = { 0 };
void sieveOfEratosthenes()
{
	for (int i = 2; i < MAXSIZE; i++)
	{
		isPrime[i] = 1;
	}
	for (int i = 2; i * i < MAXSIZE; i++)
	{
		if (isPrime[i])
		{
			for (int j = i * 2; j < MAXSIZE; j += i)
			{
				isPrime[j] = 0;
			}
		}
	}
}

埃氏篩的時(shí)間復(fù)雜度是O(n*loglogn)，效率相較于原來(lái)的暴力算法已經(jīng)有了很大的提高，但它仍然有具有一定的不足。

對(duì)于多個(gè)素?cái)?shù)的公倍數(shù)，可能會(huì)被多次篩去。

為了解決這個(gè)問(wèn)題，數(shù)學(xué)家歐拉優(yōu)化了算法，于是就有了新的篩法。

歐拉篩

歐拉篩法，簡(jiǎn)稱(chēng)歐拉篩或是歐式篩，又因?yàn)槠銸(n)的時(shí)間復(fù)雜度而被稱(chēng)為線(xiàn)性篩。

歐拉篩將合數(shù)分解為（最小質(zhì)因數(shù) * 一個(gè)合數(shù)）的形式，通過(guò)最小質(zhì)因數(shù)來(lái)判斷當(dāng)前合數(shù)是否已經(jīng)被標(biāo)記過(guò)，與埃氏篩相比，不會(huì)對(duì)已經(jīng)被標(biāo)記過(guò)的合數(shù)再進(jìn)行重復(fù)標(biāo)記，故效率更高。

下面的程序就是通過(guò)歐拉篩判斷 0 ~ MAXSIZE-1是否為素?cái)?shù)。

#define MAXSIZE 10000
int isPrime[MAXSIZE] = { 0 };
int prime[MAXSIZE];
int cnt = 0;
void sieveOfEuler()
{
	for (int i = 2; i < MAXSIZE; i++)
	{
		prime[i] = 1;
	}
	for (int i = 2; i * i < MAXSIZE; i++)
	{
		if (isPrime[i])
		{
			prime[++cnt] = i;
		}
		for (int j = 1; i * prime[j] < MAXSIZE; j++)
		{
			isPrime[i * prime[j]] = 0;
			//若i為prime[j]的倍數(shù)，終止循環(huán)，避免重復(fù)篩除
			if (i % prime[j] == 0)
                break;
		}
	}
}

在求一定范圍中的所有素?cái)?shù)時(shí)，歐拉篩具有無(wú)可比擬的優(yōu)勢(shì)，在程序設(shè)計(jì)中也經(jīng)常被采用。

到此這篇關(guān)于C++兩種素?cái)?shù)判定方法的文章就介紹到這了,更多相關(guān)C++素?cái)?shù)判定內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論