- 單次
\[\varphi(n)=n\prod_{p|n}(1-\frac{1}{p})
\]
- 積性
\[a,b互質,則\varphi(ab)=\varphi(a)\varphi(b)\\
p為質數,p|n,當p^2|n時,\varphi(n)=\varphi(n/p)p,當p^2\nmid n時,\varphi(n)=\varphi(n/p)(p-1)\\
第二行也就是:質數p,若p,q互質,則\varphi(pq)=\varphi(p)\varphi(q),否則\varphi(pq)=p\varphi(q)
- 線性篩
#include <bits/stdc++.h>
using namespace std;
int v[100000005],prime[100000005];
int main()
{
//ios::sync_with_stdio(false);
int n,q,k,m=0;
cin>>n>>q;
v[1]=1;
for(int i=2;i<=n;i++){
if(!v[i]) prime[++m]=i;
for(int j=1;j<=m;j++){
if(i*prime[j]>n) break;
v[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
while(q--){
cin>>k;
cout<<prime[k]<<endl;
}
return 0;
}
- 篩法求歐拉函數
#include <bits/stdc++.h>
using namespace std;
const int N=1e6;
int prime[N+5],eul[N+5],v[N+5];
int main()
{
int m=0;
v[1]=eul[1]=1;
for(int i=2;i<=N;i++){
if(!v[i]){
prime[++m]=i;
eul[i]=i-1;
}
for(int j=1;j<=m;j++){
if(prime[j]*i>N) break;
v[prime[j]*i]=1;
if(i%prime[j])
eul[prime[j]*i]=eul[prime[j]]*eul[i];
else {
eul[prime[j]*i]=(eul[prime[j]]+1)*eul[i];
break;
}
}
}
int T,n;
cin>>T;
while(T--){
cin>>n;
cout<<eul[n]<<endl;
}
}