欧拉函数（模板）

873. 欧拉函数 - AcWing题库

874. 筛法求欧拉函数 - AcWing题库

#include<bits/stdc++.h>
using namespace std;

int get_erlers(int x)
{   int res=x;
    for(int i=2;i<=x/i;i++)
    {
        if(x%i==0)
        {
            res=res/i*(i-1);
            while(x%i==0)
            {
                x=x/i;
            }
        }
        
    }
    if(x>1) res=res/x*(x-1);
    return res;
}

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int x;
        cin>>x;
        cout<<get_erlers(x)<<endl;
    }
}

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const  int   N=1e6+10;
bool st[N];
int prime[N],cnt;
int phi[N];
int get_erlers(int n)
{   phi[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!st[i]) 
        {
            prime[cnt++]=i;
            phi[i]=i-1;
        }
        for(int j=0;prime[j]<=n/i;j++)
        {
            st[prime[j]*i] =1;
            if(i%prime[j]==0) 
            {
                phi[prime[j]*i]=phi[i]*prime[j];//说明i中就含有prime【j】因子
                break;
            }
            phi[prime[j]*i]=phi[i]*(prime[j]-1);//i中不含prime【j】因子
        }
    }
  
}

signed main()
{
  int n;
  cin>>n;
  get_erlers(n); 
  int res=0;
    
    for(int i=1;i<=n;i++)
      res+=phi[i];
    cout<< res;
    
}