欧拉函数：
😄如果是求一个数的欧拉函数值用普通公式法（时间复杂度）： 
int eul(int n){
	int ans=n;
	
	for(int i=2;i<=n/i;i++){//找质数并处理
		if(n%i==0) ans=ans/i*(i-1);//ans*=(i-1)/i==0，也不能ans=ans*(i-1)/i，越界 
		while(n%i==0) n/=i;
	}
	if(n>1) ans=ans/n*(n-1);//ans*=(n-1)/n==0,也不能 ans=ans*(n-1)/n;容易越界 
	return ans;
}
😃如果是求1~n的欧拉函数值用线性筛法（时间复杂度为n【如果用普通公式法复杂度为】）:

1.当i mod pj ==0时，

即：



2.当i mod pj !=0时，

即，


用线性筛法模板随便把欧拉函数求出 
void euls(){
	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]=true;
			if(i%prime[j]==0){
				phi[prime[j]*i]=phi[i]*prime[j]; //+++++
				break;
			}else{
				phi[prime[j]*i]=phi[i]*(prime[j]-1);//+++++
			}
		}
	}
}
下面是两道题的代码
acwing873： 
#include <bits/stdc++.h>

using namespace std;

int t,n;

int eul(int n){
	int ans=n;
	
	for(int i=2;i<=n/i;i++){
		if(n%i==0) ans=ans/i*(i-1);//ans*=(i-1)/i==0，也不能ans=ans*(i-1)/i，越界 
		while(n%i==0) n/=i;
	}
	if(n>1) ans=ans/n*(n-1);//ans*=(n-1)/n==0,也不能 ans=ans*(n-1)/n;容易越界 
	return ans;
}

int main(int argc, char** argv) {
	cin>>t;
	while(t--){
		cin>>n;
		cout<<eul(n)<<endl;
	}
	return 0;
}


acwing874： 
#include <iostream>

using namespace std;

int n;
const int N=1000006;
int prime[N],phi[N],cnt;//phi记录各个数的欧拉函数值 
bool st[N];


void euls(){
	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]=true;
			if(i%prime[j]==0){//如果i mod pj ==0 
				phi[prime[j]*i]=phi[i]*prime[j]; //+++++
				break;
			}else{//i mod pj !=0 
				phi[prime[j]*i]=phi[i]*(prime[j]-1);//+++++
			}
		}
	}
}

int main(int argc, char** argv) {
	cin>>n;
	euls();
	long long ans=0;
	
	for(int i=1;i<=n;i++){
		ans+=phi[i];
	}
	cout<<ans<<endl;
	return 0;
}