辗转相除法

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 numbersfor (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])//从i²开始，将所有i的倍数标记为非质数//从这里我们就可以理解为什么不用枚举到sqrt(n)了。因为我们只用考虑n-1及以内的数，而sqrt(n)^2 = nfor (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;
}