一、素數的概念

素數又稱質數。一個大于1的自然數，除了1和它自身外，不能被其他自然數整除的數叫做質數；否則稱為合數。
（素數是數論中很重要的部分，所以對于一些素數的操作，需要十分的熟練）

二、判斷素數的方法

1.最基礎的方法（初學者經常用的方法）

bool isprime(int n) {for(int i=2; i<n; i++)if(n%i==0)return false;return true; } //直接從2遍歷到 n，如果之間可以被 n整除，則 n為合數，反之為素數

2.試除法（相當于上個方法的優化）

bool isprime(int n) {for(int i=2; i<=sqrt(n); i++)//寫成 i*i<=n可以稍微快一點，if(n%i==0) //因為每次循環都會計算sqrt一次，也可以用變量存起來return false;return true; } /* 如果是合數的話，那么他的因數一定會有分布在sqrt(n)的范圍內的， 就是說一個大于sqrt(n)的數要是可以被 n整除了，它的商肯定是要小于sqrt(n)的， 這時我們就不需要遍歷 n個數字，而直接遍歷sqrt(n)個數字就可以了 */

上述兩種方法完全運用了素數的概念，好理解，但是效率不高。
優化后的第二種方法也是初學者經常用的，雖然比第一種方法時間復雜度小不少，但是也是有O（n^1/2），對于一般的題目只能判斷到10¹²，所以對一些再大的數就很不友好
3.六素數法（這是在翻博客的時候發現的一種方法，在百度百科上也有提到，先放到這里）
建議看一下>>百度百科的“六素數偶”部分<<便于理解以下代碼

bool isprime(int n) {if(n==1)return false;if(n==2||n==3)return true;//1,2,3的情況特殊判斷if(n%6!=1&&n%6!=5)return false;int k=sqrt(n)+1;for(int i=5; i<k; i+=6)//這一部分和試除法類似if(n%i==0||n%(i+2)==0)return false;return true; }

這個的時間復雜度應該是 O（n^1/2/3），相比上兩種方法，效率還是提高了一些。
三、區間上的素數數量

一般來說，一個和素數相關的問題都是求[2，n]內的素數。如果用上邊的方法一個一個來判斷，時間復雜度為O（n*n^1/2），如果n比較大，可能計算機要跑幾分鐘。所以這種方法難免會超時，下面說一下可以解決一個區間上素數問題的算法。
1.埃式篩法（埃拉托斯特尼篩法）
基本思想：素數的倍數一定不是素數

（動圖出處： https://www.cnblogs.com/findwg/p/4901219.html）

const int maxx=1e7;//定義空間大小，1e7大約10MB int prime[maxx+1];//存放素數 bool visit[maxx+1];//true表示被篩掉，表示素數 int E_sieve(int n)//埃式篩，計算[2,n]內的素數 {for(int i=0; i<=n; i++)visit[i]=false;for(int i=2; i*i<=n; i++)//核心代碼if(!visit[i])for(int j=i*i; j<=n; j+=i)visit[j]=true;//標記成非素數int k=0;//作為統計個數的變量for(int i=2; i<=n; i++)if(!visit[i])prime[k++]=i;//儲存素數return k; }

時間復雜度：可以看出來，在核心代碼的那部分，一共要進行的循環次數為O（n/2+n/2+n/5+…），即O（nloglog₂n），有時候也近似看成O（n）
可以看出，埃式篩法還不錯，但是也做了一些無用功，某個數字會被篩選多次，比如12這個數字，在2和3的時候就篩選了兩次。
既然有可優化的地方，那必然有更好的算法
2.歐拉篩法（歐拉線性篩）
原理：由于所有合數都有一個最小質因子，所以在埃氏篩法的基礎上，讓每個合數只被它的最小質因子篩選一次，以達到不重復的目的。

int Oula_gprime() {int get=0;memset(v,0,sizeof(v));v[0]=v[1]=1;for(int i=2; i<=maxx; i++){//cout<<"# i = "<<i<<endl;if (!v[i])prime[get++]=i;for (int j=0; j<get&&i*prime[j]<=maxx; j++){//cout<<"j = "<<j<<"\t"<<"prime[j] = "<<prime[j]<<"\t";//cout<<"i * prime[j] = "<<i*prime[j]<<endl;v[i*prime[j]]=1;if (i%prime[j]==0)break; }//cout<<endl;}return get; }

精華部分（也算是對埃式篩法的優化部分）：

for (int j=0; j<get&&i*prime[j]<=maxx; j++) {v[i*prime[j]]=1;if (i%prime[j]==0)break; } /* 我們知道任何合數都能表示成多個素數的積。 所以，任何的合數肯定有一個最小質因子。 我們通過這個最小質因子就可以判斷什么時候不用繼續篩下去了。 當 i是 prime[j]的整數倍時，i*prime[j+1]肯定再次被篩，就跳出循環。 就比如 i=6，prime[j]=2（這時候 prime已經有了2，3，5）, i%prime[j]==0，所以就可以跳出循環。 因為在下面 prime[j]=3的時候，i*prime[j]=18， 在下一次 i=18的時候，會再循環一次，prime[j]=5的時候也一樣 */

可以發現，在下圖的 i：2~8項中，i * prime[j]的值一直沒有重復
打表也可以發現，所有的 i * prime[j]一直都不會重復出現
這也就驗證了我們一開始的對歐拉篩的另一種叫法：歐拉線性篩，
歐拉篩的時間復雜度也就的確可以做到O（n）的大小。

四、結語
無結語

總結

以上是生活随笔為你收集整理的数论--素数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。