一、判断质数

方法 1：试除法

时间复杂度：O(√n)

原理：若 n不是质数，则必有因数 ≤ √n。

bool is_prime(int n) 
{
    for (int i = 2; i * i <= n; i++) 
    {
        if (n % i == 0) 
        {
            return false;
        }
    }
    return n >= 2; // 1 不是质数
}

二、最大公约数（GCD）

方法 1：欧几里得算法（递归）

时间复杂度：O(log min(a, b))

原理：gcd(a, b) = gcd(b, a % b)

int gcd(int a, int b) 
{
    return b == 0 ? a : gcd(b, a % b);
}

方法 2：迭代版（避免递归栈溢出）

int gcd(int a, int b) 
{
    while (b != 0) 
    {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

C++17 内置函数

#include <numeric>
int gcd = std::gcd(a, b); // C++17标准库

三、最小公倍数（LCM）

公式：lcm(a, b) = a * b / gcd(a, b)

注意：先除后乘避免溢出（尤其适合大数场景）。

int lcm(int a, int b) 
{
    return a / gcd(a, b) * b;
}