给定一个整数nn，请问有多少个整数i满足条件：gcd(i, n) = 1，1<=i<=n;
输入格式
输入一行，输入一个整数n(n<=10^9)。
输出格式
输出一行，输出一个整数，表示符合条件的整数个数。
样例输入
16
样例输出
8
超时：
#include<iostream>#define MAX 1000000000using namespace std;int gcd(int a,int b){return b==0 ?a:gcd(b,a%b);}int main(){int n,count=0;cin>>n;for(int i=1;i<n;++i){if(gcd(i,n)==1){count++;}}cout<<count;return 0;}
超内存 :
#include<iostream>#include<vector>#define MAX 1000000000using namespace std;bool map[MAX];void prime(int n){map[0]=map[1]=1;for(int i=2;i*i<n;++i){if(!map[i]){for(int j=i*i;j<n;j+=i){map[j]=1;}}}}int gcd(int a,int b){return b==0 ?a:gcd(b,a%b);}int main(){int n;cin>>n;prime(n);float count=(float)n;for(int i=1;i<n;++i){if(!map[i]&&(n%i==0)){count*=(1-1/(float)i);}}printf("%.0f",count);return 0;}
ac代码解析：
主要的还是在套公式，其中的while循环是亮点
#include <iostream>using namespace std;int euler(int n){int res=n;for(int i=2;i*i<=n;i++){//因为是在遍历因子，所以找一半就行了if(n%i==0){//cout<<"因子 = "<< i<<" 此时n = ";//如果i是n的第一个因子即最小那个res=res/i*(i-1);//公式变形：//∮(n) = n*(1-P1)/P1*……*（1-Pn)/Pn//cout<<n<<endl;while(n%i==0){//寻找下一个质因子n/=i;//cout<<"while 中 = "<<n<<endl;}// cout<<"出while后 = "<<n<<endl;}}if(n>1){//大于sqrt(n)的质因子会导致循环提前结束，如42 = 2*3*7res=res/n*(n-1);}return res;}int main(){int n;cin>>n;cout<<euler(n);//euler(30);return 0;}
如果觉得《互质数的个数》对你有帮助，请点赞、收藏，并留下你的观点哦！
