前言

素数（Prime Numbers）是数学中最基础也最迷人的概念之一，同时也是计算机科学中应用最广泛的数学工具。从 RSA 加密算法到哈希表设计，从分布式一致性算法到 LeetCode 高频面试题，素数无处不在。

本文将从 Java 开发视角出发，系统讲解素数的核心概念，带你从零实现从暴力枚举到线性筛的所有主流素数算法，深入分析每种算法的原理、性能和适用场景，帮你彻底掌握素数这个编程基本功。

一、素数的基本概念

1.1 定义

素数又称质数，是指大于 1 的自然数，除了 1 和它本身之外，不能被其他任何自然数整除。

• 最小的素数是 2，也是唯一的偶素数
• 大于 2 的偶数都不是素数
• 1 既不是素数也不是合数

1.2 为什么 Java 开发者必须掌握素数算法？

1. 面试高频考点：素数判断、素数生成是校招和社招面试的基础算法题
2. 实际应用广泛：
   • 密码学：RSA、ECC 等非对称加密算法的核心就是大素数运算
   • 数据结构：哈希表通常使用素数作为数组长度，减少哈希冲突
   • 算法设计：很多经典算法（如米勒 - 拉宾素性测试）都基于素数性质
3. 锻炼算法思维：素数算法的演进过程完美体现了算法优化的核心思想

二、单个素数判断算法演进

2.1 基础暴力法（最容易想到）

原理：对于给定的数 n，检查从 2 到 n-1 的所有整数是否能整除 n。如果都不能整除，则 n 是素数。public static boolean isPrimeBruteForce(int n) { // 小于等于1的数不是素数 if (n <= 1) { return false; } // 检查从2到n-1的所有数 for (int i = 2; i < n; i++) { if (n % i == 0) { return false; } } return true; }

缺点：时间复杂度为O(n)，当 n 很大时（比如 10^6），效率极低。

2.2 优化 1：只检查到√n

原理：如果 n 有一个大于√n 的因数，那么它必然有一个对应的小于√n 的因数。因此我们只需要检查到√n 即可。public static boolean isPrime(int n) { if (n <= 1) return false; for (int i = 2; i <= Math.sqrt(n); i++) { if (n % i == 0) return false; } return true; }

3. 最终版（排除偶数）

除了 2，所有偶数都不是素数。

public static boolean isPrime(int n) { if (n <= 1) return false; if (n == 2) return true; if (n % 2 == 0) return false; // 只检查奇数 for (int i = 3; i <= Math.sqrt(n); i += 2) { if (n % i == 0) return false; } return true; }

这是单个素数判断的最优实用算法。

三、批量生成素数（埃氏筛）

当需要生成 1~n 范围内的所有素数时，使用埃拉托斯特尼筛法效率最高。

原理：先假设所有数都是素数，然后从 2 开始，把每个素数的所有倍数标记为合数

public static List<Integer> getPrimes(int n) { List<Integer> primes = new ArrayList<>(); if (n < 2) return primes; boolean[] isPrime = new boolean[n + 1]; Arrays.fill(isPrime, true); isPrime[0] = isPrime[1] = false; for (int i = 2; i <= Math.sqrt(n); i++) { if (isPrime[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)，生成 100 万以内素数仅需几毫秒。

四、算法选择建议

• 单个素数判断：使用最终版优化算法
• 批量生成素数：使用埃氏筛法
• 超大数据量（>10^7）：可以了解线性筛（欧拉筛），时间复杂度 O (n)

五、常见应用

• 密码学（RSA 加密）
• 哈希表设计（减少哈希冲突）
• 算法面试题（如 LeetCode 204. 计数质数）