簡介

• 懂得如何快速計(jì)算質(zhì)數(shù)是十分重要的

• 在篩法的基礎(chǔ)上，我們可以使用更為高級的線性篩法！

• 顧名思義，就是時間復(fù)雜度是線性的，即 O(N) ，N 為所求的質(zhì)數(shù)范圍

• 而對編程有所接觸的人，應(yīng)該都知道歐拉函數(shù) 即 φ(N)

• 聽起來高大上，其實(shí)就表示 小于等于 N 的數(shù)中與 N 互質(zhì)的數(shù)的數(shù)目

• 這在競賽中用處很大，變式也很多—— ~不明覺厲~

• 那么如何在 線性時間 內(nèi)求出 1—N 中的 質(zhì)數(shù)表 和 歐拉函數(shù)表 呢？

• 下面給出兩個算法的模板——

線性篩法

• 這個算法的本質(zhì)就是在篩法的基礎(chǔ)上，加上一個不再重復(fù)篩的退出語句

• 模板如下：

for(int i=2;i<=N;i++) {if(!bz[i]) f[++f[0]]=i;for(int j=1;j<=f[0] && i*f[j]<=N;j++){bz[i*f[j]]=true;if(i%f[j]==0) break;//極大優(yōu)化！} }

• 注釋：標(biāo)志數(shù)組為 bz[N] ， 質(zhì)數(shù)表為 f[N] 。

線性求歐拉函數(shù)

• 這個算法的本質(zhì)就是在篩法的基礎(chǔ)上，根據(jù)歐拉函數(shù)的積性性質(zhì)來處理

• 模板如下：

for(int i=2;i<=N;i++) {if(!bz[i]) phi[f[++f[0]]=i]=i-1;for(int j=1;j<=f[0] && i*f[j]<=N;j++){bz[i*f[j]]=true;if(i%f[j]==0)//同樣的極大優(yōu)化！{phi[i*f[j]]=phi[i]*f[j];break;}else phi[i*f[j]]=phi[i]*(f[j]-1);//歐拉函數(shù)的積性性質(zhì)} }

• 注釋：標(biāo)志數(shù)組為 bz[N] ， 質(zhì)數(shù)表為 f[N] ， 歐拉函數(shù)表為 phi[N] 。

總結(jié)

• 這兩個算法有兩個優(yōu)點(diǎn)：

• 短小精悍

• 復(fù)雜度線性，O(N) 處理

• 所以在以后的學(xué)習(xí)中，應(yīng)熟練掌握這兩種算法！

總結(jié)

以上是生活随笔為你收集整理的线性筛法 与 线性求欧拉函数 的计算模板的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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