日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

C++兩種素數判定方法_C 語言

作者：小嗷犬 ? 更新時間： 2022-10-04 編程語言

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

在求一定范圍中的所有素數時，歐拉篩具有無可比擬的優勢，在程序設計中也經常被采用。

原文鏈接：https://blog.csdn.net/qq_63585949/article/details/126159082

欄目分類
最近更新