给定一个整数n，请问有多少个整数i满足条件：gcd(i,n)=1，1≤i≤n。
输入格式
输入一行，输入一个整数n(n≤109)。
输出格式
输出一行，输出一个整数，表示符合条件的整数个数。
样例输入
16
样例输出
8
解题思路：这道题主要是用到数论中的短除法和欧拉函数
1.短除法分解质因子：要从最小的质数除起，一直除到结果为质数为止。
2.欧拉函数：
#include<iostream>#include<string>#include<vector>using namespace std;int main(){int n;vector<int>v;cin>>n;int ans=n;/*短除法分解质因子*/for(int i=2;i*i<=n;i++){if(n%i==0) v.push_back(i);while(n%i==0){n/=i;}}if(n>1) v.push_back(n);/*欧拉函数*/for(int i=0;i<v.size();i++){ans-=ans/v[i];}cout<<ans<<endl;return 0;}
如果觉得《蓝桥杯：互质数个数》对你有帮助，请点赞、收藏，并留下你的观点哦！
