数论算法：最大公约数与素数相关算法详解

🎯 学习目标

通过本教程，你将掌握以下数论核心算法的Java实现：

  • ✅ 最大公约数（GCD）的计算方法
  • ✅ 最小公倍数（LCM）的计算方法
  • ✅ 素数的判断算法
  • ✅ 素因数分解算法
  • ✅ 埃拉托斯特尼筛法生成素数
  • ✅ 欧拉函数计算
  • ✅ 互质数判断
  • ✅ 扩展欧几里得算法（贝祖定理）

📑 目录

📚 核心概念

数论是数学的一个分支，主要研究整数的性质。本教程将介绍数论中最基础且常用的算法，这些算法在密码学、计算机科学和工程领域都有广泛的应用。

核心概念定义：

  • 最大公约数（GCD）：两个或多个整数共有约数中最大的一个
  • 最小公倍数（LCM）：两个或多个整数公有的倍数中最小的一个
  • 素数：大于1的自然数，除了1和它本身外，不能被其他自然数整除的数
  • 素因数：一个数的素数因数
  • 互质数：公约数只有1的两个数
  • 欧拉函数：小于n且与n互质的正整数的个数

🔍 最大公约数（GCD）

🎨 核心思想

最大公约数（Greatest Common Divisor, GCD）是指两个或多个整数共有约数中最大的一个。计算最大公约数最常用的算法是欧几里得算法（又称辗转相除法），其核心思想基于以下性质：

如果 a 和 b 是两个正整数，那么 gcd(a, b) = gcd(b, a mod b)，当 b = 0 时，gcd(a, 0) = a。

💻 Java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * 使用欧几里得算法计算两个数的最大公约数（GCD）
 * @param a 第一个整数
 * @param b 第二个整数
 * @return 两个数的最大公约数
 */
public static int gcd(int a, int b) {
    // 取绝对值以处理负数
    a = Math.abs(a);
    b = Math.abs(b);
    
    // 欧几里得算法核心逻辑
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

📝 算法分析

  • 时间复杂度：O(log(min(a, b)))，因为每次迭代，较大的数至少减少一半
  • 空间复杂度：O(1)，只使用了常数额外空间
  • 应用场景：分数简化、求解线性同余方程、密码学算法等

🔍 最小公倍数（LCM）

🎨 核心思想

最小公倍数（Least Common Multiple, LCM）可以通过最大公约数计算，公式为：

LCM(a, b) = |a × b| / GCD(a, b)

这个公式基于以下原理：两个数的乘积等于它们的最大公约数和最小公倍数的乘积。

💻 Java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * 计算两个数的最小公倍数（LCM）
 * LCM(a,b) = |a*b| / GCD(a,b)
 * @param a 第一个整数
 * @param b 第二个整数
 * @return 两个数的最小公倍数
 */
public static int lcm(int a, int b) {
    if (a == 0 || b == 0) {
        return 0; // 0和任何数的最小公倍数为0
    }
    return Math.abs(a * b) / gcd(a, b);
}

🔍 素数判断

🎨 核心思想

判断一个数是否为素数，最直观的方法是检查从2到√n的每个整数是否能整除n。为了优化，可以先检查数是否能被2或3整除，然后只检查形如6k±1的数（因为所有素数大于3后，都可以表示为6k±1的形式）。

💻 Java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * 判断一个数是否为素数
 * @param n 要判断的整数
 * @return 如果n是素数返回true，否则返回false
 */
public static boolean isPrime(int n) {
    if (n <= 1) {
        return false; // 0和1不是素数
    }
    if (n <= 3) {
        return true; // 2和3是素数
    }
    if (n % 2 == 0 || n % 3 == 0) {
        return false; // 能被2或3整除的数不是素数
    }
    
    // 检查从5开始到sqrt(n)的所有数，跳过偶数和3的倍数
    // 只需要检查形式为6k±1的数
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) {
            return false;
        }
    }
    return true;
}

📝 算法分析

  • 时间复杂度：O(√n)，但由于优化，实际运行时间比简单的O(√n)算法更快
  • 空间复杂度：O(1)
  • 优化点：跳过了很多不必要的检查，尤其是偶数和3的倍数

🔍 素因数分解

🎨 核心思想

素因数分解是将一个合数分解成若干个素数的乘积的过程。算法思想是从最小的素数2开始，不断尝试将输入数除以当前素数，如果能整除，则将该素数添加到结果列表中，并继续除以该素数，直到不能整除为止。然后依次尝试更大的素数。

💻 Java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * 获取一个数的所有素因数
 * @param n 要分解的整数
 * @return n的素因数列表
 */
public static List<Integer> primeFactors(int n) {
    List<Integer> factors = new ArrayList<>();
    
    // 处理负数情况
    if (n < 0) {
        n = Math.abs(n);
        factors.add(-1);
    }
    
    // 分解2的因数
    while (n % 2 == 0) {
        factors.add(2);
        n = n / 2;
    }
    
    // 分解奇数因数
    for (int i = 3; i * i <= n; i += 2) {
        while (n % i == 0) {
            factors.add(i);
            n = n / i;
        }
    }
    
    // 如果最后剩下的数大于2，它本身就是一个素因数
    if (n > 2) {
        factors.add(n);
    }
    
    return factors;
}

📝 算法分析

  • 时间复杂度：O(√n)，最坏情况下需要检查到√n
  • 空间复杂度：O(log n)，存储素因数的列表大小

🔍 埃拉托斯特尼筛法

🎨 核心思想

埃拉托斯特尼筛法（Sieve of Eratosthenes）是一种高效的生成素数的算法。其核心思想是：

  1. 创建一个从2到n的数字表
  2. 从2开始，将每个素数的所有倍数标记为非素数
  3. 找到下一个未被标记的数，重复步骤2
  4. 当处理到√n时，所有未被标记的数都是素数

💻 Java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 使用埃拉托斯特尼筛法生成小于等于n的所有素数
 * @param n 上限值
 * @return 小于等于n的素数列表
 */
public static List<Integer> sieveOfEratosthenes(int n) {
    List<Integer> primes = new ArrayList<>();
    
    if (n < 2) {
        return primes; // 小于2的数没有素数
    }
    
    // 创建布尔数组标记是否为素数
    boolean[] isPrime = new boolean[n + 1];
    Arrays.fill(isPrime, true); // 初始假设所有数都是素数
    
    // 0和1不是素数
    isPrime[0] = isPrime[1] = false;
    
    // 筛选过程
    for (int i = 2; i * i <= n; i++) {
        if (isPrime[i]) { // 如果i是素数
            // 标记i的所有倍数为非素数
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    
    // 收集所有素数
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            primes.add(i);
        }
    }
    
    return primes;
}

📝 算法分析

  • 时间复杂度：O(n log log n)，这是一个非常高效的算法
  • 空间复杂度：O(n)，需要一个大小为n+1的布尔数组
  • 优点：对于生成范围内的所有素数，这是已知最高效的算法之一

🔍 欧拉函数

🎨 核心思想

欧拉函数φ(n)表示小于n且与n互质的正整数的个数。计算欧拉函数的公式基于数的素因数分解：

如果n的素因数分解为 n = p₁^k₁ × p₂^k₂ × … × p_m^k_m，那么：

φ(n) = n × (1 - 1/p₁) × (1 - 1/p₂) × … × (1 - 1/p_m)

💻 Java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * 计算一个数的欧拉函数值（小于n且与n互质的正整数的个数）
 * @param n 输入整数
 * @return n的欧拉函数值
 */
public static int eulerTotient(int n) {
    if (n <= 0) {
        return 0;
    }
    
    int result = n;
    
    // 分解质因数并应用欧拉函数公式
    for (int p = 2; p * p <= n; p++) {
        if (n % p == 0) {
            // p是素因数
            while (n % p == 0) {
                n = n / p;
            }
            result -= result / p;
        }
    }
    
    // 如果n本身是素数
    if (n > 1) {
        result -= result / n;
    }
    
    return result;
}

📝 算法分析

  • 时间复杂度：O(√n)
  • 空间复杂度：O(1)
  • 应用：密码学中的RSA算法、模运算中的逆元计算等

🔍 互质数判断

🎨 核心思想

两个数互质当且仅当它们的最大公约数为1。因此，可以通过计算两个数的GCD来判断它们是否互质。

💻 Java实现

1
2
3
4
5
6
7
8
9
/**
 * 判断两个数是否互质
 * @param a 第一个整数
 * @param b 第二个整数
 * @return 如果a和b互质返回true，否则返回false
 */
public static boolean areCoprime(int a, int b) {
    return gcd(a, b) == 1;
}

📝 算法分析

  • 时间复杂度：与GCD算法相同，为O(log(min(a, b)))
  • 空间复杂度：O(1)

🔍 扩展欧几里得算法

🎨 核心思想

扩展欧几里得算法是欧几里得算法的扩展，它不仅计算两个数的GCD，还能找到整数x和y，使得 ax + by = gcd(a, b)（贝祖定理）。这个算法在求解线性同余方程和计算模逆元等方面有重要应用。

💻 Java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 贝祖定理：对于任何整数a和b，存在整数x和y，使得ax + by = gcd(a,b)
 * 使用扩展欧几里得算法求解贝祖系数
 * @param a 第一个整数
 * @param b 第二个整数
 * @return 包含gcd(a,b)和系数x,y的数组 [gcd, x, y]
 */
public static int[] extendedGcd(int a, int b) {
    if (b == 0) {
        // 基本情况：a * 1 + 0 * 0 = a
        return new int[]{a, 1, 0};
    }
    
    int[] result = extendedGcd(b, a % b);
    int gcd = result[0];
    int x1 = result[1];
    int y1 = result[2];
    
    // 推导当前系数
    int x = y1;
    int y = x1 - (a / b) * y1;
    
    return new int[]{gcd, x, y};
}

📝 算法分析

  • 时间复杂度：O(log(min(a, b)))
  • 空间复杂度：O(log(min(a, b)))，由于递归调用栈
  • 应用：求解线性同余方程、计算模逆元、密码学中的密钥生成等

⚡ 性能分析

算法 时间复杂度 空间复杂度 适用场景
最大公约数 O(log(min(a, b))) O(1) 分数简化、模运算
最小公倍数 O(log(min(a, b))) O(1) 分数运算、周期计算
素数判断 O(√n) O(1) 快速判断单个素数
素因数分解 O(√n) O(log n) 数论分析、密码学
埃拉托斯特尼筛法 O(n log log n) O(n) 生成范围内所有素数
欧拉函数 O(√n) O(1) 模运算、密码学
互质数判断 O(log(min(a, b))) O(1) 密码学、数论分析
扩展欧几里得算法 O(log(min(a, b))) O(log(min(a, b))) 求解线性同余方程

💡 总结与应用

🎯 主要应用领域

  1. 密码学：RSA算法、椭圆曲线加密等都依赖于数论算法
  2. 计算机科学：哈希函数、随机数生成、数据压缩等
  3. 工程应用：信号处理、编码理论、计算机图形学等
  4. 数学研究：解决各种数论问题和证明

💻 完整工具类示例

下面是一个完整的数论工具类，包含了上述所有算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 数论工具类，提供常用的数论算法实现
 */
public class NumberTheoryUtils {
    
    // 所有方法实现...
    
    // 测试主函数
    public static void main(String[] args) {
        // 测试最大公约数
        System.out.println("GCD(48, 18) = " + gcd(48, 18)); // 应该输出6
        
        // 测试最小公倍数
        System.out.println("LCM(4, 6) = " + lcm(4, 6)); // 应该输出12
        
        // 测试素数判断
        System.out.println("Is 17 prime? " + isPrime(17)); // 应该输出true
        System.out.println("Is 15 prime? " + isPrime(15)); // 应该输出false
        
        // 测试素因数分解
        System.out.println("Prime factors of 100: " + primeFactors(100)); // 应该输出[2, 2, 5, 5]
        
        // 测试埃拉托斯特尼筛法
        System.out.println("Primes <= 30: " + sieveOfEratosthenes(30)); // 应该输出所有小于等于30的素数
        
        // 测试欧拉函数
        System.out.println("Euler's totient of 10: " + eulerTotient(10)); // 应该输出4
        
        // 测试互质判断
        System.out.println("Are 8 and 15 coprime? " + areCoprime(8, 15)); // 应该输出true
        
        // 测试扩展欧几里得算法
        int[] extendedResult = extendedGcd(48, 18);
        System.out.println("Extended GCD(48, 18): " + 
                          "gcd=" + extendedResult[0] + 
                          ", x=" + extendedResult[1] + 
                          ", y=" + extendedResult[2]);
    }
}

📚 进阶学习资源

  • 算法导论：第31章详细介绍了数论算法
  • 密码学原理与实践：介绍了数论在密码学中的应用
  • Competitive Programming 3：包含更多高级数论算法