第一課時
復習及引入
質數判斷
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個或以上的質數的積”,那么換個角度去理解,合數一定是某個質數的倍數。
那么,當我確定一個數為質數,我自然可以將它所有的范圍內的倍數(\(\ge 2\))找出來,這些倍數一定是合數。
也就是若\(p\)為質數,那么\(j\times p,(j\ge2,j\times p\le n )\) 就是合數。
以30以內的篩選為例
配合圖片,嘗試手動模擬篩選過程。
算法步驟:
- 設置一個標記數組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
過程中可發現很多數字被重復篩選了。
接下來就是減少重復篩選,以提高運行速度。
觀察重復的數字 :
可發現質數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;
}
第二課時
歐拉篩
模擬出埃氏篩的篩選過程。
即便進行了一定的優化,但是依舊存在數字被重復篩選的問題。它的復雜度依舊不變\(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;//返回質數個數
}
浙公網安備 33010602011771號