28 数论 欧拉函数

28 数论 欧拉函数

1 判断一个数是否为欧拉函数

//判断一个数是否为欧拉函数，套用欧拉函数公式=a*(1-1/p1)*(1-1/p2)*...*(1-1/pk),其中pi是a的约数
#include
using namespace std;
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
    int a;
    scanf("%d",&a);
    int res=a;//
    for(int i=2;i<=a/i;i++)//求一个数的约数
       if(a%i==0)
       {
           res=res/i*(i-1);//套用公式
           while(a%i==0) a/=i;
       }
       if(a>1) res=res/a*(a-1);
       printf("%dn",res);
}
    return 0;
}

2 欧拉筛（线性筛）来求1~n范围内每个数的欧拉个数和

//欧拉筛（线性筛）来求1~n范围内每个数的欧拉个数和，用到了线性筛的方法
#include
using namespace std;
typedef long long ll;
const int N=1e6+10;
int primes[N],cnt;//存质数
int phi[N];//存这个数的欧拉数
bool st[N];//用来判断一个数是否为质数
ll get_eulers(int n)
{
    phi[1]=1;//初始化1的欧拉数只为1
    for(int i=2;i<=n;i++)
    {
        if(!st[i])//假如是质数
        {
            primes[cnt++]=i;//把这个点放进质数中
            phi[i]=i-1;//质数的欧拉数为i-1，因为除了自己其他数全互质
        }
        for(int j=0;primes[j]<=n/i;j++)//判断一个数有没有最小因子
        {
            st[primes[j]*i]=true;//用最小质因子去筛合数，标记素数的倍数为合数
            if(i%primes[j]==0)//假如没有则跳出来
            {
                phi[primes[j]*i]=phi[i]*primes[j];//欧拉数为第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;
scanf("%d",&n);
printf("%lldn",get_eulers(n));//输出结果
    return 0;
}