最大公约数和最小公倍数

1. 最大公约数
正整数a和b的最大公约数是a和b的所有公约数的最大的那个
可以用欧几里得算法（辗转相除法）获得
$gcd(a, b) = gcd(b, a \% b)$

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

# 利用三元运算符
def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)

2. 最小公倍数
正整数a和b的最小公倍数是 $a \times b / gcd(a, b)$
所以可以得到 $lcm(a, b) \times gcd(a, b) == a \times b$
在其它语言中为了防止a*b溢出，先算a/gcd(a, b)

def lcm(a, b):
    return a / gcd(a, b) * b

3. 扩展欧几里得算法
已知正整数a和b，求$ax + by = gcd(a, b)$的解x和y

质数（素数）

素数判定：一个大于1的自然数，除了1和自身，不能被其它整数整除，就是素数（质数）
能整除为合数
1. 暴力整除判断是否是素数

def isPrime(a):
    if a < 2:
        return False
    for i in range(2, int(sqrt(a)) + 1):    # [2, 根号(a) + 1) 判断是否能整除
        if a % i == 0:
            return False
    return True

2. 筛法 提前把前n个数是否是素数标出来，时间复杂度$O(n loglog n)$
对于任意一个大于 1 的正整数 n，那么它的 x 倍就是合数（x > 1）

prime = []  # 存储前n个素数
is_prime = [False] * N  # 前n个数是否为素数

def Eratosthenes(n):
    is_prime[0] = is_prime[1] = False
    for i in range(2, n + 1):
        is_prime[i] = True
    
    for i in range(2, n + 1):
        if is_prime[i]:
            prime.append(i)
            if i * i > n:
                continue
            # 因为倍数2 到 i - 1 我们之前筛过了，这里直接从倍数i开始
            for j in range(i * i, n + 1, i):
                is_prime[j] = False

互质

两个整数的最大公约数为1

print("yes" if gcd(a, b) == 1 else "No")

质因数分解

将一个整数分解成为多个质数的乘积
$180 = 2^2 \times 3^2 \times 5 ^ 1$

模运算

几何

1. 点到点的距离
2. 点到线的距离
3. 点到面的距离