[數論]-----歐拉篩法的應用

文章目錄

• 1.求1~n之間的所有質數
• 2.求1~n之間所有自然數的歐拉函數φ（x）
• 3.求1~n之間的每個數的因子個數
• • 詳細推導：
  • 代碼：
• 4.求1~n之間每個數的因數和
• • 詳細的推導：
  • 代碼：
• 篩法求莫比烏斯函數

1.求1~n之間的所有質數

歐拉篩法核心思想：每個合數只被自己的最小質因子篩一次

2.求1~n之間所有自然數的歐拉函數φ（x）

3.求1~n之間的每個數的因子個數

詳細推導：

代碼：

void Euler(){memset(isprime,1,sizeof isprime); d[1]=1;for(int i=2;i<=n;i++){if(isprime[i]){prime[++tot]=i;d[i]=2;num[i]=1;}for(int j=1;j<=tot&&i*prime[j]<=n;j++){isprime[i*prime[j]]=0;if(i%prime[j]==0){d[i*prime[j]]=d[i]/(num[i]+1)*(num[i]+2);num[i*prime[j]]=num[i]+1; break;}else{d[i*prime[j]]=d[i]*2;num[i*prime[j]]=1;}}} }

4.求1~n之間每個數的因數和

詳細的推導：

代碼：

O(n)

void Euler() {ans[1]=1;for(LL i=2;i<=r;i++){if(!vis[i]){prime[++cnt]=i;s[i]=psum[i]=i+1;//i是質數 vis[i]=1;}for(LL j=1;j<=cnt&&prime[j]<=r/i;j++){vis[i*prime[j]]=1;if(i%prime[j]==0){psum[i*prime[j]]=psum[i]*prime[j]+1;s[i*prime[j]]=s[i]/psum[i]*psum[i*prime[j]];break;}else{psum[i*prime[j]]=prime[j]+1;s[i*prime[j]]=s[i]*s[prime[j]];}}} }

篩法求莫比烏斯函數

總結

以上是生活随笔為你收集整理的欧拉筛法的应用的全部內容，希望文章能夠幫你解決所遇到的問題。

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