如果不会线性筛素数的话,建议先看这篇博客了解一下线性筛素数。
欧拉函数(积性函数都可以线性筛)主要是在线性筛素数的基础上得到的
欧拉函数: φ(n)=n∗∏(1−pi1) 其中 pi为 n的质因子
所以:
1、当 n 为质数的时候 φ(n)=n−1
对于 2和3 设 d=pn 其中 p为 n 的最小质因子
2、当 p 是 d 的某个质因子时, 则 φ(n)=φ(d)∗p
3、当 p 与 d 互质时, φ(n)=φ(d)∗φ(p)
good luck and have fun!!!
附上代码:
void eular(int n)
{
memset(vis,0,sizeof(vis));
phi[1]=1;
prime[0]=0;
for(int i=2;i<=n;i++)
{
if(!vis[i])
{
prime[++prime[0]]=i;
phi[i]=i-1;
}
for(int j=1;j<=prime[0]&&i<=n/prime[j];j++)
{
vis[i*prime[j]]=1;
if(i%prime[j]==0)
{
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
phi[i*prime[j]]=phi[i]*(prime[j]-1);
}
}
}