常见算法

常见算法，持续整理中

数字的运算

最大公约数

int gcd(int a, int b)
{
  return b == 0 ? a : gcd(b, a % b);
}

辗转相除法，以上算法要求a与b都是正整数，不要求a与b的大小关系。

数字的约数个数

long divisors(long a)
{
    if (a == 1)
        return 1;
    else if (a < 1)
        return 0;
	
    // 求得质因子
    unordered_map<long, long> primeSubNums;
    long ini = 2;
    while(a>1)
    {
        for(long i= ini; i<=a; i++)
        {
            if(a%i == 0)
            {
                a = a/i;
                primeSubNums[i]++;
                ini = i;
                break;
            }
        }
    }

	 // 判断是否为质数，如果是合数则使用质因子求得约数个数
    if (primeSubNums.size() == 1 && primeSubNums[a] > 0)
    {
        return primeSubNums.size() + 1;
    }
    else
    {
        long res = 1;
        for (auto i : primeSubNums)
        {
            res *= (i.second + 1);
        }
        return res;
    }
}