欧几里得算法||辗转相除法

欧几里得算法： gcd(a, b) = gcd(b, a%b);

gcd(48, 36)
=   gcd(36, 12)
=   gcd(12, 0)

gcd(128, 100)
=   gcd(100, 28)
=   gcd(28, 16)
=   gcd(16, 12)
=   gcd(12, 4)
=   gcd(4, 0)
    
最小公倍数：lcm(a, b) = a * b / gcd(a, b)

int a, b;
cin >> a >> b;

//gcd(a, b) = gcd(b, a%b)
while(b > 0){
    int t = a % b;
    a = b;
    b = t;
}
cout << a;

唯一分解定理

定义：任意一个大于 1 的整数，都能唯一分解为若干个质数的乘积。

36 = 2 * 2 * 3 * 3

int n;
cin >> n;

for(int i = 2; i <= n/i; i ++ ){
    while(n % i == 0){
        cout << i << ' ';
        n = n / i;
    }
}
if(n > 1) cout << n;

质数筛法(埃氏筛)

bool st[10000005];//st[i]等于 1 表示不是质数

void primes(int n){
    //筛出 1 ～ n 之间所有的质数
    st[1] = 1;
    for(int i = 2; i*i <= n; i ++ ){
        if(st[i] == false){
            //如果这个数字没有被标记
            //    2～i-1都不是 i 的因数
            //接下标记 i 的倍数
            //当i = 10的时候，i*2 i*3 i*4 ... i*9一定会被更小的数字标记
            for(int j = i*i; j <= n; j += i)
                st[j] = 1;
        }
    }
}