素数判定方法

素数判定与筛法：从朴素试除到高效埃氏筛

素数（质数）是算法竞赛中数论板块的核心考点，本文系统整理朴素试除法、埃氏筛法和欧拉筛法的核心原理、实战模板及经典例题，所有代码均为竞赛级极简实现，可直接复制使用。

一、朴素试除法：单个素数判定的最优解

1.1 核心原理

素数的定义是：大于 1 的自然数，且除了 1 和它本身外无其他正因数。
试除法是判定单个素数的基础方法，核心优化逻辑：

• 原始逻辑：检查 2 ~ n-1 是否能整除 n（时间复杂度 O(n)）；
• 优化逻辑：若 n 是合数，则必有一个因数 ≤ √n，因此只需检查 2 ~ √n（时间复杂度 O(√n)）；
• 溢出规避：代码中用 i <= n / i 替代 i * i <= n，避免整数乘法溢出。

1.2 竞赛级极简模板

/**
* 判定单个数字是否为素数（竞赛最优实现）
* @param n 待判定的数字
* @return true=素数，false=非素数
*/
public static boolean isPrime(int n) {
if (n < 2) return false; // 小于2的数必非素数
for (int i = 2; i <= n / i; ++i) { // 避免i*i溢出，等价于i<=√n
if (n % i == 0) return false; // 存在因数，非素数
}
return true;
}

1.3 经典例题：疑似素数

题目描述

输入正整数 n，求 1~n 中“疑似素数”的个数。“疑似素数”定义：十进制下各位数字之和为素数的正整数。

完整AC代码

import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int ans = 0;
for (int i = 1; i <= n; i++) {
int temp = i, sum = 0;
// 计算各位数字之和
while (temp > 0) {
sum += temp % 10;
temp /= 10;
}
if (isPrime(sum)) ans++; // 判定和是否为素数
}
System.out.println(ans);
scan.close();
}

// 素数判定核心函数
public static boolean isPrime(int n) {
if (n < 2) return false;
for (int i = 2; i <= n / i; ++i) {
if (n % i == 0) return false;
}
return true;
}
}

二、埃氏筛法（Sieve of Eratosthenes）：大范围素数筛选神器

2.1 核心原理

当需要判定 10^6 级别的大范围素数时，试除法逐个判定效率极低，埃氏筛法通过“标记倍数”实现批量筛选，核心思想：

时间复杂度：O(n log log n)，在 10^6 范围内几乎是线性时间，效率远超试除法。

2.2 竞赛级极简模板

/**
1. 埃氏筛法筛选1~n的所有素数
2. @param n 筛选上限
3. @return 标记数组：v[i]=true 表示i非素数，v[i]=false 表示i是素数
*/
public static boolean[] eratosthenesSieve(int n) {
boolean[] v = new boolean[n + 1];
v[0] = v[1] = true; // 0和1不是素数
for (int i = 2; i <= n; ++i) {
if (!v[i]) { // i是素数，标记其所有倍数
for (int j = 2 * i; j <= n; j += i) {
v[j] = true;
}
}
}
return v;
}

优化：
1.把埃氏筛中标记倍数的内层循环起始点从 2 * i 改为 i * i ，核心原因是：i 的 2~i-1 倍已经被更小的素数标记过了，从 i*i 开始能减少冗余操作。
2. 把外层循环的上限改为 Math.sqrt(n)（等价于 i * i <= n），因为大于 √n 的数的倍数已经被更小的素数标记过了，无需遍历。

public static boolean[] eratosthenesSieve(int n) {
boolean[] v = new boolean[n + 1];
v[0] = v[1] = true;
// 外层循环优化：仅遍历到 √n
for (int i = 2; i * i <= n; ++i) {
if (!v[i]) {
// 内层循环从 i*i 开始
for (int j = i * i; j <= n; j += i) {
v[j] = true;
}
}
}
return v;
}

2.3 经典例题：小明的素数对

题目描述

给定正整数 n，计算 1~n 中有多少对不同的素数 (p, q)（p < q），满足 q – p 也是素数。

完整AC代码

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
// 1. 埃氏筛法筛选素数
boolean[] isNotPrime = eratosthenesSieve(n);

// 2. 收集所有素数
List<Integer> primes = new ArrayList<>();
for (int i = 0; i <= n; i++) {
if (!isNotPrime[i]) primes.add(i);
}

// 3. 统计符合条件的素数对
int ans = 0;
for (int i = 0; i < primes.size(); i++) {
for (int j = i + 1; j < primes.size(); j++) {
int diff = primes.get(j) – primes.get(i);
if (diff <= n && !isNotPrime[diff]) { // 差需在筛法范围内
ans++;
}
}
}
System.out.println(ans);
scan.close();
}

// 埃氏筛法核心函数
public static boolean[] eratosthenesSieve(int n) {
boolean[] v = new boolean[n + 1];
v[0] = v[1] = true;
for (int i = 2; i <= n; ++i) {
if (!v[i]) {
for (int j = 2 * i; j <= n; j += i) {
v[j] = true;
}
}
}
return v;
}
}

三、欧拉筛法（线性筛）：极致高效的素数筛选

3.1 核心原理

埃氏筛法存在“重复标记合数”的问题（如 12 会被 2 和 3 各标记一次），欧拉筛法通过“最小质因数唯一标记”实现线性时间复杂度 O(n)，核心逻辑：

核心优化：i % p == 0 时停止，因为此时 p 是 i 的最小质因数，i*p 的最小质因数也必然是 p，若继续用更大的素数标记，会导致重复操作（如 i=4、p=2 时，4%2=0，停止；若继续用 p=3 标记 12，会与 i=6、p=2 标记 12 重复）。

3.2 竞赛级极简模板

/**
* 欧拉筛法（线性筛）筛选1~n的所有素数
* @param n 筛选上限
* @return 标记数组：v[i]=true 表示i非素数，v[i]=false 表示i是素数
*/
public static boolean[] eulerSieve(int n) {
boolean[] v = new boolean[n + 1]; // true=非素数，false=素数
v[0] = v[1] = true; // 0和1不是素数
ArrayList<Integer> primes = new ArrayList<>(); // 存储已找到的素数

for (int i = 2; i <= n; ++i) {
if (!v[i]) primes.add(i); // 未被标记，是素数
// 用已找到的素数标记合数
for (int p : primes) {
if (i * p > n) break; // 超出范围，停止标记
v[i * p] = true; // 标记i*p为合数
if (i % p == 0) break; // 核心：最小质因数标记，避免重复
}
}
return v;
}

3.3 经典例题：小明的素数对（欧拉筛改造版）

只需将原代码中的 eratosthenesSieve 替换为 eulerSieve 即可（其他不用改变），时间效率更高（尤其当 n > 10^6 时）：

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
// 1. 欧拉筛法筛选素数（替换原埃氏筛）
boolean[] isNotPrime = eulerSieve(n);

// 2. 收集所有素数
List<Integer> primes = new ArrayList<>();
for (int i = 0; i <= n; i++) {
if (!isNotPrime[i]) primes.add(i);
}

// 3. 统计符合条件的素数对（逻辑与原代码一致）
int ans = 0;
for (int i = 0; i < primes.size(); i++) {
for (int j = i + 1; j < primes.size(); j++) {
int diff = primes.get(j) – primes.get(i);
if (diff <= n && !isNotPrime[diff]) {
ans++;
}
}
}
System.out.println(ans);
scan.close();
}

// 欧拉筛法核心函数
public static boolean[] eulerSieve(int n) {
boolean[] v = new boolean[n + 1];
v[0] = v[1] = true;
ArrayList<Integer> primes = new ArrayList<>();

for (int i = 2; i <= n; ++i) {
if (!v[i]) primes.add(i);
for (int p : primes) {
if (i * p > n) break;
v[i * p] = true;
if (i % p == 0) break;
}
}
return v;
}
}

四、核心知识点总结

五、竞赛实战拓展

本文所有代码均经过竞赛场景验证，可直接用于AC解题。欧拉筛法是算法竞赛中大范围素数筛选的首选。