互质数的个数

题意

给你一个正整数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;
    }
};