数学相关

gcd / lcm

• 3.1.1. 最大公因数与最小公倍数
  有三条性质

1. gcd(a, b) = gcd(b, a)
2. gcd(a, 0) = a
3. a > b => gcd(a, b) = gcd(a mod b, b)
4. gcd(a, b) ✖️ lcm(a, b) = a ✖️ b

算法

int gcd(int a, int b)
{
	while (a && b && (a > b ? a %= b : b %= a));

	return a + b;
}

质数