质数
质数:除了 1 和该数自身外,无法被其他自然数整除的数。
注:
- 2 和 3 是所有素数中唯一两个连着的数
- 2 是唯一一个为偶数的质数
- 质数的个数是无穷的
1 | // 求规定范围内的质数 |
最大公约数
如果数 a 能被数 b 整除,a 就叫做 b 的倍数,b 就叫做 a 的约数。
如 15 能被 3 整除,15 是 3 的倍数,3 是 15 的约数
12、16 的公约数有 1、2、4,其中最大的一个是 4,4 是 12 与 16 的最大公约数,一般记为 (12, 16) = 4
辗转相除法(欧几里得算法): gcd(a, b) = gcd(b, a mod b)
1 | // 欧几里得算法 求两个数的最大公约数 |
最小公倍数
4 和 6 的公倍数有 12、24,……,其中最小的是 12,一般记为 [4, 6] = 12
最大公约数 和 最小公倍数 的关系:(a, b) * [a, b] = a * b
1 | // 公式法 求两个数的最小公倍数 |