求一个数的欧拉函数用上一题的方法
求1到N每一个的欧拉函数用筛法(用之前的线性筛法)
一个质数P的欧拉函数就是P-1
phi[i]=i-1;//质数的欧拉函数为1到i-1
i%pj==0时,pj是i的一个质因子,i的欧拉函数已经有一个(1-1/pj)了,欧拉函数跟这个质数的次数是没有关系的所以 pj*i的欧拉函数=i的欧拉函数乘以一个pj
phi[i*primes[j]]=phi[i]*primes[j];
i%pj!=0时pj是ipj的最小质因子
pji的欧拉函数==i的欧拉函数乘以(pj-1)
phi[primes[j]*i]=phi[i]*(primes[j]-1);
本题代码
#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
typedef long long LL;
int primes[N],cnt;
int phi[N];
bool st[N];
LL get_eulers(int n)
{
for(int i=2;i<=n;i++)
{
phi[1]=1;//与1互质的数只有他自己
if(!st[i])
{
primes[cnt++]=i;
phi[i]=i-1;//质数的欧拉函数为1到i-1
}
for(int j=0;primes[j]<=n/i;j++)
{
st[primes[j]*i]=true;
if(i%primes[j]==0)
{
phi[i*primes[j]]=phi[i]*primes[j];
break;
}
phi[primes[j]*i]=phi[i]*(primes[j]-1);
}
}
LL res=0;
for(int i=1;i<=n;i++)
res+=phi[i];
return res;
}
int main()
{
int n;
cin>>n;
cout<<get_eulers(n);
return 0;
}