找素數(shù)

暴力求解

• 時間復(fù)雜度： O(n*sqrt(n))

原理

暴力求解是對[m,n]的每一個整數(shù)都判斷是否為素數(shù)，由數(shù)學(xué)可知，一個數(shù)i的因數(shù)關(guān)于sqrt(i)對稱分布,故我們只需判斷[2,sqrt(i)]的整數(shù)中有沒有i的因數(shù)即可

代碼

vector<int> fuckingFindPrime(int m,int n) {vector<int> prime;if(m<=n){for(int i=m; i<=n; i++){bool flag = true;for(int j=2; j<=sqrt(i); j++) //需要調(diào)用math.h頭文件{if(!(i%j)){flag = false;break;}}if(!flag) continue;else prime.push_back(i);}} return prime; }

埃氏篩法

• 時間復(fù)雜度： O(n*log(n))

原理

首先，2是最小質(zhì)數(shù)，所以先把2在n以內(nèi)的所有倍數(shù)篩選掉。然后，3也是質(zhì)數(shù)，故把3的所有倍數(shù)篩選掉。4不是質(zhì)數(shù)，且4為2的倍數(shù)，已經(jīng)被篩選掉，跳過。5是質(zhì)數(shù)。。。。然后依次類推，最后剩下的就都是質(zhì)數(shù)了。

代碼

vector<int> EratosthenesSieve(int n) {vector<int> num;vector<int> prime;for(int i=0; i<=n; i++)num.push_back(i);//把[0,n]的整數(shù)初始化num[1] = 0; //1公認不是素數(shù)，把1去掉for(int i=2; i<=n; i++){if(!num[i])continue;//被置為0的數(shù)不是素數(shù)，所以跳過本輪循環(huán)去判斷下一個位置prime.push_back(i); //是素數(shù)，保存到prime中//以下為埃氏篩的關(guān)鍵，參考上文的“原理”部分for(int j=i; i*j<=n&&j<n; j++)num[i*j] = 0;}return prime; }

提示

如果要尋找區(qū)間[m,n]的素數(shù)，只需用埃氏篩打表n以內(nèi)的素數(shù)到向量prime（或數(shù)組），然后在prime中找到不小于m的最小素數(shù)，一直輸出到不大于n為止

比如，尋找[50,90]的素數(shù)，代碼可以如下

int main() {vector<int> prime = EratosthenesSieve(90);int i=0;while(prime[i]<50) i++;for(int j=i; prime[j]<=90; j++)cout << prime[j] << " ";cout << endl;return 0; }

當(dāng)然，這只是個簡單的例子，你也可以用更高效的查找算法于prime中尋找，因為本文主題為尋找素數(shù)，所以查找方面不過多敘述

歐拉篩(線性篩)

• 時間復(fù)雜度： O(n)

原理

其將合數(shù)分為 合數(shù) = 最小質(zhì)因數(shù)*合數(shù) 的形式，通過最小質(zhì)因數(shù)判斷是否被標(biāo)記。故相對于埃氏篩，歐拉篩不會反復(fù)標(biāo)記一個合數(shù)，效率更高。

代碼

vector<int> EulerSieve(int n) {int pNum = 0; //記錄素數(shù)的個數(shù)vector<int> prime;vector<bool> isPrime; //用于標(biāo)記//對標(biāo)記向量初始化for(int i=0; i<n; i++)isPrime.push_back(false);for(int i=2; i<=n; i++){if(!isPrime[i]) //沒有被篩選過，則為素數(shù){pNum++;prime.push_back(i);}for(int j=0; j<pNum && i*prime[j]<=n; j++){isPrime[i*prime[j]] = true; //將已經(jīng)記錄的素數(shù)倍數(shù)標(biāo)記//下方為歐拉篩的核心if(!(i%prime[j])) break;}}return prime; }

核心

歐拉篩妙就妙在它的核心處

? 若

? i是prime[j]的整數(shù)倍k

? 則

? i · prime[j+1] = k · prime[j] · prime[j+1] = k · prime[j+1] · prime[j]

? i · prime[j+1]為 prime[j] 的整數(shù)倍，不需要被標(biāo)記，prime[j+2]…prime[j+…] 同理

? 故

? 該推導(dǎo)告訴我們不需要去標(biāo)記后面的數(shù)，直接跳出循環(huán)即可

提示

歐拉篩法同埃氏篩一樣為打表方法，想要獲取[m,n]的素數(shù)要去查表

《新程序員》：云原生和全面數(shù)字化實踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的寻找素数算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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