今天完成力扣每日一题：公因子的题目，用数学最优思路AC题目，分享完整解题逻辑。

题目思路

两个数的全部公因子，一定是这两个数最大公约数（gcd）的因数

1.先用辗转相除法，求出a、b的最大公因数g

2.遍历1~g的数字，统计可以整除g的数字个数，就是最终公因子数量

辗转相除法求gcd原理

不断用大数对小数取余，把小数赋值给大数，余数赋值给小数，直到余数为0，此时大数就是最大公约数。

例子：a=12，b=6

gcd(12,6)=6,遍历1、2、3、6一共4个因数，和样例完全匹配

C++完整运行代码

class Solution{

public:

       int c gcd(int a,int b){

                while(b){

                          int temp=a%b;

                          a=b;

                         b=temp;

                     }

                      return a;

                  }

                   int commonFactors(int a,int b){

                      int g=gcd(a,b);

                      int cnt=0;

                       for(int i=1;i<=g;i++){

                             if(g%i==0) cnt++;

                       }

                       return cnt;

              }

};

算法复杂度优化

暴力枚举两数所有因数时间复杂度高，转为最大公约数枚举，数字范围大幅缩小，运行效率大幅提升。