数论问题（算法村第十三关黄金挑战）

辗转相除法

8 和 12 的最大公因数是 4，记作 gcd(8,12)=4。辗转相除法最重要的规则是：

若 mod 是 a ÷ b 的余数, 则gcd(a, b) = gcd(b, mod)，直到a % b == 0时，返回 b的值

gcd(546, 429)

= gcd(429, 117)

= gcd(117, 78)

= gcd(78, 39)

= 39

public int gcb(int a, int b)
{
    int mod = 0;
    do
    {
        mod = a % b;
        a = b;
        b = mod;
    }while (mod != 0);

    return a;	//此时 a 的值==最后一个除数
}

质数

判断一个数是否是质数

public boolean isPrime(int num)
{
    int sqrt = (int)Math.sqrt(num);

    for (int i = 2; i <= sqrt; i++)
        if(num % i == 0)
            return false;

    return true;
}

计数质数

204. 计数质数 - 力扣（LeetCode）

给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。

示例 1：

输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7

提示：

• 0 <= n <= 5 * 10

超时的暴力解法

public int countPrimes(int n)
{
    int count = 0;

    // 0 and 1 are not prime numbers
    for (int i = 2; i < n; i++)
        if(isPrime(i))
            count++;

    return count;
}

public boolean isPrime(int num)
{
    int sqrt = (int)Math.sqrt(num);

    for (int i = 2; i <= sqrt; i++)
        //如果 num 是合数，那 sqrt 两边一定存在一对 nums 的因数  
        if(num % i == 0)
            return false;

    return true;
}

时间复杂度：O(n * n^ 1/2)
空间复杂度：O(1)

一般来说题目里 n 的规模达到 10^5 及以上时，需要实现的程序的时间复杂度最高只能是 O(n logn)

埃氏筛

204. 计数质数 - 力扣（LeetCode）

public int countPrimes(int n)
{
    boolean[] primes = new boolean[n];
    Arrays.fill(primes, true);   //初始化为全部都是质数

    //从2枚举到sqrt(n)（不含）
    for (int i = 2; i * i < n; i++)
    {
        if (primes[i])
            //从i2开始，将所有i的倍数标记为非质数
            //从这里我们就可以理解为什么不用枚举到sqrt(n)了。因为我们只用考虑n-1及以内的数，而sqrt(n)^2 = n
            for (int j = i * i; j < n; j += i)
                primes[j] = false;
    }

    //统计质数的个数
    int count = 0;
    for (int i = 2; i < n; i++)
        if (primes[i]) count++;

    return count;
}

丑数

把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）

根据丑数的定义，0 和负整数不是丑数。

当 n>0 时，若 n 是丑数，则 n 可以写成 n = 2^a + 3^b + 5^c 的形式，其中 a,b,c 都是非负整数。

特别地，当 a,b,c 都是 0 时，n=1。所以1也是丑数

对 n 反复除以 2,3,5，直到 n 不再包含质因数 2,3,5。若剩下的数等于 1，则说明 n 不包含其他质因数，n是丑数；否则，说明n包含其他质因数，n不是丑数。

public boolean isUglyNum(int num)
{
    if (num <= 0)
        return false;

    int[] factors = {2, 3, 5};

    //如果num能整除任何一个因子，则继续除以这个因子
    //每次整除会使以factor为底的指数减一
    //当指数为零时，跳出while循环
    for (int factor : factors)
        while (num % factor == 0)
            num =  num / factor;

    //若num能被所有质因子整除，则num最后==1，即num为丑数
    return  num == 1;
}