Number數論

歐拉函數PHI

篩法歐拉函數

歐拉函數

在數論，對正整數n，歐拉函數是小于或等于n的正整數中與n互質的數的數目（是以φ(1)=1）。此函數以其首名研究者歐拉命名(Euler’s totient function)，它又稱為Euler’s totient function、φ函數、歐拉商數等。 例如φ(8)=4，因為1,3,5,7均和8互質。 從歐拉函數引伸出來在環論方面的事實和拉格朗日定理構成了歐拉定理的證明。

百度百科連結: link.

歐拉定理是用來闡述素數模下，指數同餘的性質。

對于歐拉定理還有幾個相關的結論：

如果n為素數，則φ( n ) = n-1

因為對于n來說，小于等于n的正整數有n個，但是因為n是素數，n與其本身并不互質，是以有n-1個數跟它互質。

若n為質數p的k次方 那麼φ( n ）=(p-1)pk

n = pk(p是質數），是以一個數要想跟n互質的話應該不是p的倍數，p的倍數有p * p, 2 * p, 3 * p……pn-1 * p,共有pn-1個，小于等于n的正整數有pk個，是以φ( n ）= (p-1)pk.

埃氏篩

時間複雜度為O(n loglog n)，如果一個數的因數除了1和他本身沒有其他因數的數是素數，是以如果他是除了一和它本身的一個數的倍數的話那麼他就是合數，是以我們就從2開始，如果這個數沒有被通路過說明之前他沒有素數因子，是以我們就把在2到n中他的倍數給标記，如果一個數被通路過，說明這個數是合數，可以直接跳過了，一直找下去就好。

第二重循環我們在找的時候是從i*i開始的，是因為i * (比i小的數)，我們之前找過了，就像2 * i, 3 * i ……是以不會被重複篩查。

#include<iostream>
#include<cstring>
using namespace std;
int visited[1000001];
int main(){
	int n;
	cin >> n;
	memset(visited,0,sizeof(visited));
	for(int i=2;i<=n;i++){
		if(visited[i]) continue;
		else{
			for(int j = i*i;j<=n;j+=i){
				visited[j] = 1;
			}
		}
	}
	for(int i=2;i<=n;i++){
		if(visited[i]==0) cout << i << " ";
	}
	return 0;
}
           

但是其中還有一個需要我們注意的地方就是就像30，我們在篩查2的倍數的術後篩查過了，但是篩查5的時候同時又被篩查了一遍，為了解決這種合數被重複篩查的情況我們就有了時間複雜度是O(n)的歐拉線性篩法。

歐拉線性篩法

為此我們需要知道的一些結論：

①每一個合數都可以分解為一個質數與另外一個數相乘（合數是指在大于1的整數中除了能被1和本身整除外，還能被其他數（0除外）整除的數，是以隻要是合數就能夠被分解，依次遞歸分解下去）；

②

if(i%prime[j]==0) break;

如果這個數能夠被prime整除，說明這個數可以分解為prime[j]和另外一個大于等于prime[j]的數相乘，另外的這個數又可以分解成為若幹個大于等于prime[j]的數相乘，是以如果繼續下去會導緻計算判斷重複，故在此處停止，繼續向下執行，由此保證了O(n)的複雜度。

代碼如下：

#include<iostream>
#include<cstring>
using namespace std;
int vis[10001];//判斷是否通路過
int prime[100001];//用以存儲找到的質數
int cnt = 0;
int main(){
	int n;
	cin >> n;
	memset(vis,0,sizeof(vis));
	for(int i=2;i<=n;i++){
		if(!vis[i]) prime[cnt++] = i;
		for(int j=0;j<cnt && i*prime[j]<=n;j++){
			vis[i*prime[j]] = 1;
			if(i%prime[j]==0) break;
		}
	}
	for(int i=0;i<cnt;i++){
		cout << prime[i] << " ";
	}
	return 0;
}