数论知识点

1.判断质数

1. 因数的对称性 如果一个大于 1 的整数 num 不是质数，那么它必定可以分解成两个正整数 a 和 b 的乘积，即 num = a * b，其中 1 < a ≤ b < num。 例如，对于数字 16，它可以写成 16 = 2 * 8、16 = 4 * 4 等形式。可以发现，在这些因数对中，较小的因数（如 2 和 4）总是小于或等于 num 的平方根。 从数学角度来看，假设 a ≤ b，那么 a * b = num，由此可得 a * a ≤ a * b = num，即 a ≤ √num。所以，只要检查到 √num 就可以确定 num 是否有除 1 和它自身以外的因数。
2. 代码中使用 i <= num / i 替代 i <= √num 的原因 在代码实现时，直接使用平方根运算（如 Math.sqrt(num)）会有一些缺点： - 性能开销：平方根运算相对来说是比较耗时的操作，会增加程序的运行时间。 精度问题：在计算机中，浮点数运算可能会存在精度误差，对于某些特殊的数值，可能会导致判断结果不准确。 而使用 i <= num / i 这种形式，避免了平方根运算，不仅提高了代码的执行效率，还避免了浮点数精度带来的问题。它本质上和 i * i <= num 是等价的，通过简单的乘法和比较操作就能达到相同的效果。

public static boolean is_prime(int num) {
    // 从 2 开始遍历到 num 的平方根（即 num / i）
    for (int i = 2; i <= num / i; i++) {
        // 如果 num 能被 i 整除，说明 num 不是质数
        if (num % i == 0) {
            return false;
        }
    }
    // 如果没有找到能整除 num 的数，说明 num 是质数
    return true;
}

2.最大公约数

这段代码实现的是使用欧几里得算法（辗转相除法）来计算两个整数 a 和 b 的最大公约数（GCD，Greatest Common Divisor）。

欧几里得算法原理 欧几里得算法基于一个重要的数学性质：两个整数 a 和 b（a >= b）的最大公约数等于 b 和 a % b（a 除以 b 的余数）的最大公约数，即 gcd(a, b) = gcd(b, a % b)。 这个性质可以通过以下方式证明：

设 a 和 b 的最大公约数为 d，即 a = m * d，b = n * d，其中 m 和 n 是互质的整数（即它们的最大公约数为 1）。 根据除法的定义，a = k * b + r，其中 k 是商，r 是余数（0 <= r < b），也就是 r = a % b。 将 a = m * d 和 b = n * d 代入 a = k * b + r 中，得到 m * d = k * n * d + r，进一步变形为 r = (m - k * n) * d。 这说明 r 也是 d 的倍数，即 d 是 b 和 r 的公约数。 假设存在一个比 d 更大的数 d' 是 b 和 r 的公约数，那么 b = s * d'，r = t * d'，代入 a = k * b + r 中可得 a = k * s * d' + t * d' = (k * s + t) * d'，这意味着 d' 也是 a 和 b 的公约数，与 d 是 a 和 b 的最大公约数矛盾。所以，d 也是 b 和 r 的最大公约数，即 gcd(a, b) = gcd(b, a % b)。

public static int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

3.最小公倍数

最小公倍数（LCM）与最大公约数（GCD）的关系 对于任意两个正整数 a 和 b，它们的最小公倍数和最大公约数之间存在以下关系：
$$LCM(a, b) = \frac{a \times b}{GCD(a, b)}$$
这个公式的原理是：a 和 b 的乘积等于它们的最大公约数和最小公倍数的乘积。

public static int lcm(int a, int b){
       return a/gcd(a,b)*b;
}
public static int gcd(int a, int b) {
     while (b != 0) {
         int r = a % b;
         a = b;
         b = r;
     }
     return a;
 }

在计算 a * b / gcd(a, b) 时，为了避免整数溢出，代码中采用了 a / gcd(a, b) * b 的方式。因为 a 是 gcd(a, b) 的倍数，所以 a / gcd(a, b) 是一个整数，这样可以减少溢出的风险。

综上所述，这段代码通过先计算两个整数的最大公约数，再利用最大公约数和最小公倍数的关系，成功计算出了两个整数的最小公倍数。

4.质数筛

得到 小于等于n 的所有质数

朴素筛法

boolean[] st = new boolean[N];
int[] primes = new int[N];

public static void get_primes(int n){
    for(int i = 2;i <= n;i++){
        if(!st[i]){
            primes[cnt++] = i;
        }
        for(int j = i + i;j <= n;j += i){
            st[j] = true;
        }
    }
}

埃氏筛法

boolean[] st = new boolean[N];
int[] primes = new int[N];

public static void get_primes(int n){
    for(int i = 2;i <= n;i++){
        if(!st[i]){
            primes[cnt++] = i;
            for(int j = i + i;j <= n;j += i){
                st[j] = true;
            }
        } 
    }
}