蓝桥杯算法提高VIP-欧拉函数 （C++描述，时间复杂度sqrt（n））

解题思路:        欧拉函数：phi(n)=n(1-(1/p1))(1-(1/p2))....(1-(1/pk)) ；

                        p代表的是所有质因子（均不同）

                        例如16：因子有 2  4 6 8 16  其中质因子只有2 所以   phi(16)=n(1-(1/2))=8;

                        在例如

                    36：因子有2 3 6 12 36  其中质因子为2，3，phi（36）=n*(1-(1/2))*(1-(1/3))=12
注意事项:
                    因为可能爆int问题 所以n*(1-(1/p))可以转化为n/p*(p-1);
参考代码:

#include <bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin>>n;
	int ans=n;
	for(int i=2;i*i<=n;i++){
		if(n%i==0){
			ans=ans/i*(i-1);//n*(1-(1/p))转化为n/p*(p-1)
			while(n%i==0)n/=i;//划去所有i的倍数，类似于素数筛的原理
		}
	}
	if(n>1)ans=ans/n*(n-1);//最后如果n大于1说明还有一个质数因子
	cout<<ans<<endl;
	return 0;
}