第一課時

復習及引入

質數判斷

bool isPrime(int x){
    if(x<2) return false;
    for(int i=2;i*i<=x;i++){
        if(x%i==0) return false;
    }
    return true;
}

復雜度分析 $O(\sqrt{n})$

引入問題，輸入n($1\leq n\leq10^6$)個數字($0\leq x \leq 10^6$)，判斷每個數是不是質數？

利用已有知識，程序框架：

while(n--){//循環n次
    cin>>x;//輸入數字
    if(isPrime(x)){//判斷x是否是質數
        cout<<"Yes\n";
    }else{
        cout<<"No\n";
    }
}

我們來分析下時間復雜度 $O(n\sqrt{x})$ 。

思考，當前數據范圍下是否能在1s時限內求出答案。

回答：$10^6\times 10^3 = 10^9$ 會超時。

進一步，該怎么去更快的處理大范圍內的質數？

我們提前設置一個標記數組prime[N] ,提前標記好數字的質數狀態，這樣就能減少重復判斷。

引出質數篩法

核心思想：唯一分解定理

每個大于1的自然數，要么本身就是質數，要么可以寫為2個或以上的質數的積，而且這些質因子按大小排列之后，寫法僅有一種方式。

埃氏篩

? 埃拉托斯特尼選篩法，簡稱埃氏篩。要得到自然數n以內的全部素數，必須把不大于根號n的所有素數的倍數剔除，剩下的就是素數。

來理解下埃氏篩的思想

根據唯一分解定理的前半截“每個大于1的自然數，要么本身就是質數，要么可以寫為2個或以上的質數的積”，那么換個角度去理解，合數一定是某個質數的倍數。

\[\begin{split} & 6=2\times 3\\ & 12=2\times 2\times 3\\ & 15=3\times 5 \end{split} \]

那么，當我確定一個數為質數，我自然可以將它所有的范圍內的倍數($\ge 2$)找出來，這些倍數一定是合數。

也就是若$p$為質數，那么$j\times p,(j\ge2,j\times p\le n )$ 就是合數。

以30以內的篩選為例

\[\begin{split} & \ \ 2\ :\ 4\ 6\ 8\ 10\ 12\ 14\ 16\ 18\ 20\ 22\ 24\ 26\ 28\ 30\\ & \ \ 3\ :\ 6\ 9\ 12\ 15\ 18\ 21\ 24\ 27\ 30\\ & \ \ 5\ :\ 10\ 15\ 20\ 25\ 30\\ & \ \ 7\ :\ 14\ 21\ 28\\ & 11\ :\ 22\\ & 13\ :\ 26\\ & 17\ :\\ & 19\ :\\ & \ \ \ ... \end{split} \]

配合圖片，嘗試手動模擬篩選過程。

算法步驟：

設置一個標記數組vis[N],初始化為0。0-是質數 1-不是質數
處理特殊值 0 ，1
從2開始，依次將范圍內的質數的倍數標記為1（非質數）

初版:

const int N=1e6+5;
bool vis[N];
void esieve(int n){//標記0~n的數字的質數狀態,并統計質數個數
	vis[0]=vis[1]=1;//0，1屬于非質數
	for(int i=2;i<=n;i++){//標記剩下的2~n的數字的狀態
		if(vis[i]==0){//判斷i是不是質數 思考：為什么這樣就能判斷i是質數？
			for(int j=2*i;j<=n;j+=i){//遍歷范圍內的i的倍數
				vis[j]=1;//將倍數標記為1（非質數）
			}
		}
	}
}

思考：第6行，為什么這樣就能判斷i是質數？

解答：狀態數組初始化為0，循環的方向是從小到大，過程中質數的在范圍內的倍數都會被篩選掉。那么到i如果還是0,意味著質因子中不包含前面的這些質數，一個數在2~i-1這個范圍內沒有因子，那么他就是質數。

優化1

根據約數的分布性，一個數n如果是合數，其中較小的約數范圍一定是在$\sqrt{n}$ 內。那么對于$\sqrt{n}+1$~$n$ 范圍內的合數，一定可以被$2$~$\sqrt{n}$ 內的質數篩選掉。

const int N=1e6+5;
bool vis[N];
void esieve(int n){//標記0~n的數字的質數狀態,并統計質數個數
    vis[0]=vis[1]=1;
	for(int i=2;i*i<=n;i++){//標記剩下的2~n的數字的狀態 優化：到根號n即可停止
		if(vis[i]==0){//判斷i是不是質數 
			for(int j=2*i;j<=n;j+=i){//遍歷范圍內的i的倍數
				vis[j]=1;//將倍數標記為1（非質數）
			}
		}
	}
}

優化2

\[\begin{split} & \ \ 2\ :\ 4\ 6\ 8\ 10\ 12\ 14\ 16\ 18\ 20\ 22\ 24\ 26\ 28\ 30\\ & \ \ 3\ :\ 6\ 9\ 12\ 15\ 18\ 21\ 24\ 27\ 30\\ & \ \ 5\ :\ 10\ 15\ 20\ 25\ 30\\ & \ \ 7\ :\ 14\ 21\ 28\\ & 11\ :\ 22\\ & 13\ :\ 26\\ & 17\ :\\ & 19\ :\\ & \ \ \ ... \end{split} \]

過程中可發現很多數字被重復篩選了。

接下來就是減少重復篩選，以提高運行速度。

觀察重復的數字 :

\[\begin{split} 6& = 2\times 3\\ &=3 \times 2\\ 10&=2\times 5\\ &=5\times 2 \end{split} \]

可發現質數p與比它小的質數相乘得到的乘積，一定在之前被那么更小的質數篩過。那么篩選的時候直接從$p^2$開始篩選，避免重復。

const int N=1e6+5;
bool vis[N];
void esieve(int n){//標記0~n的數字的質數狀態,并統計質數個數
    vis[0]=vis[1]=1;
	for(int i=2;i*i<=n;i++){//標記剩下的2~n的數字的狀態 優化：到根號n即可停止
		if(vis[i]==0){//判斷i是不是質數 
			for(int j=i*i;j<=n;j+=i){//遍歷范圍內的i的倍數 從i*i開始，減少重復篩選
				vis[j]=1;//將倍數標記為1（非質數）
			}
		}
	}
}

時間復雜度$O(nloglogn)$

復雜度分析鏈接：http://www.rzrgm.cn/dc93/p/3930362.html

習題鞏固

題目描述

今天是貝茜的生日，為了慶祝自己的生日，貝茜邀你來玩一個游戲。

貝茜讓 N ($1\leq N\leq 10^5$ ) 頭奶牛坐成一個圈。除了$ 1 $號與$ N $號奶牛外，$i$ 號奶牛與$ i?1 $號和 $i+1$ 號奶牛相鄰。$N $號奶牛與 $1$ 號奶牛相鄰。農夫約翰有一個桶，里面裝滿了很多紙條，每一張紙條上寫了一個不一定是獨一無二的 $1 $到$10^6$ 的數字。

接著每一頭奶牛 $i$ 從桶中取出一張紙條$ A_i$ 。每頭奶牛輪流走上一圈，同時拍打所有手上數字能整除在自己紙條上的數字的牛的頭，然后做回到原來的位置。牛們希望你幫助他們確定，每一頭奶牛走上一圈時能夠拍打的牛的數量。

輸入格式

第一行包含一個整數n

第二行到n+1行每行包含一個整數$A_i$

輸出格式

共n行，每行包含一個整數，代表被拍打的牛的數量

樣例輸入

5
2
1
2
3
4

樣例輸出

2
0
2
1
3

分析

根據題意概括一下，就是給出數列a,對于第i項的$a_i$求出數列中有多少個是他的約數。

暴力

遍歷其它元素，統計他的約數的個數即可。復雜度$O(n^2)$

for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
        if(i!=j&&a[i]%a[j]==0){
            cnt++;
        }
    }
}

優化

利用埃氏篩的思想，統計數組中的內容，對它的倍數做的貢獻即可。

#include <iostream>
#include <cstdio>
using namespace std;
const int N=1e6+5;
int a[N],cnt[N],M=0;//cnt[x]=k x在數列中的約數個數為k
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		cnt[a[i]]++;//記錄次數
		M=max(M,a[i]);//求值得最大范圍
	}
	for(int i=M;i>=1;i--){//從到大小進行遍歷
		if(!cnt[i]) continue;//沒出現過的直接跳過
		for(int j=2;j*i<=M;j++){//找范圍內的i的倍數
			if(cnt[j*i])//如果倍數也是在數列中的值
				cnt[j*i]+=cnt[i];//倍數對應的在數列中的因數個數增加
		}
	}
	for(int i=1;i<=n;i++){
		cout<<cnt[a[i]]-1<<endl;//注意要去掉自己
	}
	return 0;
}

第二課時

歐拉篩

模擬出埃氏篩的篩選過程。

\[\begin{split} & \ \ 2\ :\ 4\ 6\ 8\ 10\ 12\ 14\ 16\ 18\ 20\ 22\ 24\ 26\ 28\ 30\\ & \ \ 3\ :\ 9\ 12\ 15\ 18\ 21\ 24\ 27\ 30\\ & \ \ 5\ :\ 25\ 30\\ & \ \ 7\ :\ \\ & 11\ :\ \\ & 13\ :\ \\ & 17\ :\\ & 19\ :\\ & \ \ \ ... \end{split} \]

即便進行了一定的優化，但是依舊存在數字被重復篩選的問題。它的復雜度依舊不變$O(nloglogn)$ 。

此時，若能讓每個數字只被篩選一次，必然能大大地降低時間復雜度，減少運行時間，理論上的時間復雜度為$O(n)$ 。

這種每個數字只被篩一遍的篩法叫做歐拉篩，也被稱作線性篩。

那么，關鍵是，如何實現這一算法？

我們依舊利用唯一分解定理來實現。之前的埃氏篩，利用到了唯一分解定理的前半段，這次我們利用好它的后半截。

每個大于1的自然數，要么本身就是質數，要么可以寫為2個或以上的質數的積，而且這些質因子按大小排列之后，寫法僅有一種方式。

合數對應的分解因式，只要我們將這小質因子按大小排列好，那么分解式子就是唯一的。

我們要利用他的唯一性來做文章。我們只要能不重復的構造出這樣的“唯一的質數序列”，那么必然不會重復篩選了。

此時我們將任意的一個數字都可看做為一個唯一的質數序列，如$12$可看作是序列$2\times 2\times 3$ 。此時我們只要再找個質數，與這樣的質數序列組合即可構成新的質數序列。

需要注意的是，如何防止重復？也就是怎么保證構造出來的序列的唯一性？我們新的質數組合進去之后，只要不破壞序列整體的有序性，即可實現不重復。假設，我們每次將質數是加在序列的前頭，那么只需要$P_{新質數}\leq 序列的最小質因子$ 即可保證整體有序。

例如通過 $2\times 2\times 3$ 進行新序列的組合的話，只能加質數2，形成新序列$2\times 2\times 2\times 3=24$。如果是序列$15=3\times 5$的話只能和2，3組合，形成新序列$2\times 3\times5=30$和$3\times 3\times5=45$ 。

這樣，我們在實現的時候就要在之前的基礎上多一個質數表存放質數，好利用這些質數構成質數序列。

模板

時間復雜度$O(n)$

const int N=1e8+5;
bool vis[N];//標記數組
int prime[N/10];//質數表，存放質數
int erla(int n){
	vis[0]=vis[1]=1;//0.1不是質數
	int cnt=0;//統計質數的個數
	for(int i=2;i<=n;i++){
		if(!vis[i]){//判斷i是不是質數
			prime[cnt++]=i;//將質數存到質數表中
		}
		//遍歷質數表 新序列 prime[j]*i
		for(int j=0;prime[j]*i<=n&&j<cnt;j++){
			vis[prime[j]*i]=1;//標記組成的序列為非質數
			if(i%prime[j]==0) break;//prime[j]是i的最小質因子 ，不能繼續組合，避免重復
		}
	}
	return cnt;//返回質數個數
}

思考：14行操作的意義，思考為什么這么做就能不重復地篩選？

回答：質數表中的質數是從小到大的，在遍歷質數表時，可看做滿足$p_j\le i的最小值因子$ ，遍歷到的質數與i構成的序列就不重復。當滿足整除條件時，prime[j]就是等于i的最小質因子，再遍歷下去，就不滿足質數從小到大的關系。

習題鞏固

哥德巴赫猜想（升級版）

問題描述

求1~N中素數的個數。

輸入格式

一行一個整數N。

輸出格式

一行一個數，表示素數的個數。

輸入樣例

10

輸出樣例

4

數據范圍

對于40%的數據，$1\leq N\leq 10^6$。

對于80%的數據，$1\leq N\leq 10^7$。

對于100%的數據，$1\leq N\leq 10^8$。

分析

注意數據范圍，套歐拉篩模板即可。

第三課時

歐拉函數

? 在數論中，對正整數n歐拉函數是小于或等于n的正整數中與n互質的數的數目。

? 例如$\phi(1)=1,(1)$,$\phi(8)=4,(1,3,5,7)$。如果i是素數，則$\phi(i)=i-1$。

設p為質數

三個性質：

$\phi(p)=p-1$
$i\ mod\ p = 0,\phi(i\times p)=p\times \phi(i)$
$i\ mod\ p \ne 0,\phi(i\times p)=(p-1)\times \phi(i)$

實現代碼

時間復雜度$O(n)$

bool vis[N];//標記數組
int prime[N];//質數表，存放質數
int phi[N];
int erla(int n){
	vis[0]=vis[1]=1;//0.1不是質數
	int cnt=0;//統計質數的個數
	phi[1]=1;//1的歐拉函數值是1
	for(int i=2;i<=n;i++){
		if(!vis[i]){//判斷i是不是質數
			prime[cnt++]=i;//將質數存到質數表中
			phi[i]=i-1;//性質1
		}
		//遍歷質數表 新序列 prime[j]*i
		for(int j=0;prime[j]*i<=n&&j<cnt;j++){
			vis[prime[j]*i]=1;//標記組成的序列為非質數
			if(i%prime[j]==0){
				phi[i*prime[j]]=prime[j]*phi[i];//性質2
				break;//prime[j]是i的最小質因子 ，不能繼續組合，避免重復
			}else{
				phi[i*prime[j]]=(prime[j]-1)*phi[i];//性質3
			}
		}
	}
	return cnt;//返回質數個數
}

posted on 2022-03-08 21:55 咸魚愛學習閱讀(163) 評論(0) 收藏舉報

刷新頁面返回頂部