数论初步

GCD算法:

唯一分解定理： 算术基本定理可表述为：任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积

推论：最小公倍数LCM

gcd(a,b)∗lcm(a,b)=a∗b $$gcd(a,b)*lcm(a,b) = a*b$$

Eratosthenes 筛法：

对于不超过n的每个负整数p，删除 2p,3p,4p,...,$2p, 3p, 4p,...,$ 当处理完所有数后，还没被删除的为素数。