【题解】互质数的个数
互质数的个数
题意
给你一个正整数N（不超过 )，请你求出小于等于N的正整数中与N互质的数字的个数。
（两个整数a与b互质当且仅当它们的最大公约数为1）
解法1
可以用枚举法求出小于等于n的整数中与n互质的数的个数
时间复杂度：
空间复杂度：
代码
class Solution {
public:
/**
*
* @param n int整型
* @return int整型
*/
int gcd(int a,int b)
{
if(b==0)return a;
else return gcd(b,a%b);
}
int euler(int n) {
int ans=0;
for(int i=1;i<=n;i++)
if(gcd(i,n)==1)ans++;
return ans;
// write code here
}
};解法2
以上解法时间复杂度太高，无法通过所有测试数据。
数论函数中欧拉函数 的定义即为小于或等于n的正整数中与n互质的数的数目，
欧拉函数的计算公式为
其中 为x的所有质因数。
我们可以在对一个数进行质因数分解的同时求它的欧拉函数值。
时间复杂度：
空间复杂度：
代码
class Solution {
public:
/**
*
* @param n int整型
* @return int整型
*/
int euler(int n) {
int res = n,t=n;
for(int i=2;i*i<=t;i++)
if(n%i==0)
{
while(n%i==0)n/=i;
res=res/i*(i-1);
}
if(n>1)res=res/n*(n-1);
return res;
}
};
查看7道真题和解析
投递蚂蚁集团等公司10个岗位