练习题：互质数个数

题目

样例

思路

求n的欧拉函数。

代码

#include <iostream>using namespace std;int euler(int n){int res=n,mid=n;for(int i=2;i*i<=mid;i++)if(mid%i==0){res=res/i*(i-1);//减去res中i倍数的个数while(mid%i==0) mid/=i;}if(mid>1) return res/mid*(mid-1);else return res;}int main(){int n;cin>>n;cout<<euler(n);}

如果觉得《练习题：互质数个数》对你有帮助，请点赞、收藏，并留下你的观点哦！