C++兩種素數判定方法

2022-08-09 14:03:13

1.什麼是素數

素數又稱質數。一個大於1的自然數，除了1和它自身外，不能被其他自然數整除的數叫做素數；否則稱為合數（規定1既不是素數也不是合數）。

在許多的程式設計題目中，都會涉及到素數的判斷，那我們該如何有效判斷素數呢？

2.素數的兩種判斷方法

（1）暴力法

從 2 到 √n

根據素數的定義，我們可以使用逐個試除的方式來判斷素數，如果能為要判斷的數找到一個除了1和自身以外的因數，那麼它就是合數；反之，就是素數。

而這樣的因數的範圍必然在 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;
}

該函數就可以判斷輸入的數是否為素數。

這個範圍還可以更進一步地縮小。

6n-1與6n+1

數學上有一個定理，除了2和3外，只有形如6n-1和6n+1的自然數可能是素數，這裡的n是大於等於1的整數。

如何理解這個定理呢？

所有自然數都可以寫成6n,6n+1,6n+2,6n+3,6n+4,6n+5這6種。那麼我們就可以得到下表。

自然數	是否可能是素數
6n	不可能，為2的倍數
6n+1	可能
6n+2	不可能，為2的倍數
6n+3	不可能，為3的倍數
6n+4	不可能，為2的倍數
6n+5	可能

其中6n+5可以寫作6n-1，所以除了2和3的素數必然形如6n-1或6n+1。

於是我們可以寫出如下程式碼。

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;
}

優化後的演演算法具有更高的效率。

（2）篩法

暴力演演算法雖然可以判斷某個數是否為素數，但是當它面對大量需要判斷的資料時，它的效率會顯得十分低下，我們也有更好地方法來求一定範圍裡的素數，它就是我們的篩法。

篩法，顧名思義，就是將合數從資料中篩除，剩下的自然就都是素數了。

篩法也分為兩種，讓我們來逐一介紹。

埃氏篩

埃拉託斯特尼篩法，簡稱埃氏篩，是一種由希臘數學家埃拉託斯特尼所提出的一種簡單檢定素數的演演算法。

要得到自然數n以內的全部素數，必須把不大於根號n的所有素數的倍數剔除，剩下的就是素數。

下面的程式就是通過埃氏篩判斷 0 ~ MAXSIZE-1是否為素數。

#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;
			}
		}
	}
}

埃氏篩的時間複雜度是O(n*loglogn)，效率相較於原來的暴力演演算法已經有了很大的提高，但它仍然有具有一定的不足。

對於多個素數的公倍數，可能會被多次篩去。

為了解決這個問題，數學家尤拉優化了演演算法，於是就有了新的篩法。

尤拉篩

尤拉篩法，簡稱尤拉篩或是歐式篩，又因為其O(n)的時間複雜度而被稱為線性篩。

尤拉篩將合數分解為（最小質因數 * 一個合數）的形式，通過最小質因數來判斷當前合數是否已經被標記過，與埃氏篩相比，不會對已經被標記過的合數再進行重複標記，故效率更高。

下面的程式就是通過尤拉篩判斷 0 ~ MAXSIZE-1是否為素數。

#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]的倍數，終止迴圈，避免重複篩除
			if (i % prime[j] == 0)
                break;
		}
	}
}

在求一定範圍中的所有素數時，尤拉篩具有無可比擬的優勢，在程式設計中也經常被採用。

到此這篇關於C++兩種素數判定方法的文章就介紹到這了,更多相關C++素數判定內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！