素数判定方法详解：从基础试除法到优化策略

        素数是只能被1和自身整除的正整数。素数的判定是数论中的基础问题，也是算法竞赛中的常见考点。

---

一、知识点

1. 素数的定义：
   素数（质数）是大于1的自然数，且只能被1和自身整除。

2. 试除法：
   通过遍历从2到sqrt(n)​的所有整数，判断是否能整除n。如果能整除，则n不是素数。

3. 试除法的优化：

   • 优化1：将试除范围从[2, n-1]缩小到[2, sqrt(n)​]。

   • 优化2：仅用[2, sqrt(n)​]内的素数试除，避免用合数试除。

4. 时间复杂度：

   • 未优化的试除法：O(n)。

   • 优化后的试除法：O(sqrt(n))。

---

二、试除法及其优化

1. 基础试除法

• 原理：遍历从2到sqrt(n)​的所有整数，检查是否能整除n。

• 代码实现：

  bool isPrime(long long n) {if (n <= 1) return false; // 1不是素数for (long long i = 2; i <= sqrt(n); i++) {if (n % i == 0) return false; // 能整除，不是素数}return true; // 是素数
  }

• 说明：

  • sqrt(n)：只需遍历到sqrt(n)​​，因为如果n有大于sqrt(n)​的因子，必然有小于sqrt(n)​的因子。

  • 时间复杂度：O(sqrt(n)​)。

2. 试除法的第一次优化

• 原理：仅用[2, sqrt(n)​​]内的素数试除，避免用合数试除。

• 实现步骤：

  1. 预先生成[2, sqrt(n)​]内的所有素数（如用筛法）。

  2. 用这些素数试除n。

• 代码实现：

  bool isPrimeOptimized(long long n, const vector<long long>& primes) {if (n <= 1) return false; // 1不是素数for (long long p : primes) {if (p * p > n) break; // 超过sqrt(n)，停止if (n % p == 0) return false; // 能整除，不是素数}return true; // 是素数
  }

• 说明：

  • primes：预先生成的素数列表（如用埃氏筛法生成）。

  • 时间复杂度：O(sqrt(n)​/log⁡n)，因为素数密度约为log⁡n。

3. 试除法的第二次优化

• 原理：结合筛法，动态生成素数列表，避免预先生成。

• 实现步骤：

  1. 使用筛法（如埃氏筛法）动态生成[2, sqrt(n)​​]内的素数。

  2. 用这些素数试除n。

• 代码实现：

  vector<long long> generatePrimes(long long limit) {vector<bool> isPrime(limit + 1, true);vector<long long> primes;for (long long i = 2; i <= limit; i++) {if (isPrime[i]) {primes.push_back(i);for (long long j = i * i; j <= limit; j += i) {isPrime[j] = false;}}}return primes;
  }bool isPrimeOptimized2(long long n) {if (n <= 1) return false; // 1不是素数long long limit = sqrt(n);vector<long long> primes = generatePrimes(limit);return isPrimeOptimized(n, primes);
  }

• 说明：

  • generatePrimes：生成[2, sqrt(n)​​]内的素数列表。

  • 时间复杂度：O(sqrt(n) ​log⁡ log⁡n)（筛法复杂度）。

---

三、代码说明

1. 基础试除法：

   • 适用于小规模数据（n≤10^12）。

   • 实现简单，但效率较低。

2. 第一次优化：

   • 通过预先生成素数列表，减少试除次数。

   • 适用于需要多次判断素数的场景。

3. 第二次优化：

   • 动态生成素数列表，避免预先生成。

   • 适用于单次判断素数且n较大的场景。

四、例题解析

P1036 [NOIP 2002 普及组] 选数 - 洛谷 

算法代码： 

#include<bits/stdc++.h>  // 包含所有标准库头文件
using namespace std;     // 使用标准命名空间int n, k;                // n: 数组长度, k: 需要选择的元素个数
int a[20];               // 存储输入的数组
int ans;                 // 记录满足条件的组合数// 判断一个数是否为素数
bool is_prime(int s) {if (s <= 1) {        // 1及以下的数不是素数return false;}for (int i = 2; i <= sqrt(s); i++) {  // 遍历2到sqrt(s)if (s % i == 0) {  // 如果s能被i整除，说明s不是素数return false;}}return true;         // 否则s是素数
}// 深度优先搜索（DFS）函数
// cnt: 当前已选择的元素个数
// sum: 当前已选择元素的和
// p: 当前选择的起始位置
void dfs(int cnt, int sum, int p) {if (cnt == k) {      // 如果已经选择了k个元素if (is_prime(sum)) {  // 判断这些元素的和是否为素数ans++;       // 如果是素数，答案加1}return;         // 返回上一层递归}for (int i = p; i < n; i++) {  // 从位置p开始选择元素dfs(cnt + 1, sum + a[i], i + 1);  // 递归选择下一个元素}
}int main() {cin >> n >> k;       // 输入数组长度n和需要选择的元素个数kfor (int i = 0; i < n; i++) {  // 输入数组元素cin >> a[i];}dfs(0, 0, 0);        // 调用DFS函数，初始状态：已选0个元素，和为0，起始位置为0cout << ans;         // 输出满足条件的组合数return 0;            // 程序结束
}

1. 问题描述

• 输入：一个长度为n的数组a，以及一个整数k。

• 目标：从数组a中选择k个元素，使得这些元素的和为素数。统计所有满足条件的组合数。

---

2. 设计思路

（1）核心问题分解

• 子问题1：如何判断一个数是否为素数？

• 子问题2：如何从数组中选择k个元素，并计算它们的和？

• 子问题3：如何统计所有满足条件的组合数？

（2）解决子问题1：素数判断

• 方法：使用试除法。

  • 遍历从2到sqrt（n）​的所有整数，检查是否能整除n。

  • 如果能整除，则n不是素数；否则，n是素数。

• 代码实现：

  bool is_prime(int s) {if (s <= 1) return false; // 1及以下的数不是素数for (int i = 2; i <= sqrt(s); i++) {if (s % i == 0) return false; // 能整除，不是素数}return true; // 是素数
  }

（3）解决子问题2：选择k个元素并计算和

• 方法：使用深度优先搜索（DFS）遍历所有可能的组合。

  • 从数组中选择k个元素，确保不重复选择。

  • 在DFS过程中，记录当前已选择的元素个数、当前和以及选择的起始位置。

• 代码实现：

  void dfs(int cnt, int sum, int p) {if (cnt == k) { // 已选择k个元素if (is_prime(sum)) ans++; // 如果和为素数，答案加1return;}for (int i = p; i < n; i++) { // 从位置p开始选择dfs(cnt + 1, sum + a[i], i + 1); // 递归选择下一个元素}
  }

（4）解决子问题3：统计满足条件的组合数

• 方法：在DFS过程中，每当找到一个满足条件的组合（和为素数），就将计数器ans加1。

• 代码实现：

  int ans = 0; // 初始化计数器
  dfs(0, 0, 0); // 调用DFS函数
  cout << ans; // 输出结果

---

3. 代码实现步骤

（1）输入部分

• 读取数组长度n和需要选择的元素个数k。

• 读取数组a的元素。

  cin >> n >> k;
  for (int i = 0; i < n; i++) {cin >> a[i];
  }

（2）DFS函数

• 参数说明：

  • cnt：当前已选择的元素个数。

  • sum：当前已选择元素的和。

  • p：当前选择的起始位置（避免重复选择）。

• 递归终止条件：

  • 当cnt == k时，检查sum是否为素数。如果是，则ans++。

• 递归过程：

  • 从位置p开始，依次选择数组中的元素，并递归调用DFS。

    void dfs(int cnt, int sum, int p) {if (cnt == k) {if (is_prime(sum)) ans++;return;}for (int i = p; i < n; i++) {dfs(cnt + 1, sum + a[i], i + 1);}
    }

（3）输出结果

• 调用DFS函数后，输出满足条件的组合数ans。

  dfs(0, 0, 0);
  cout << ans;

---

4. 时间复杂度分析

• is_prime函数：O（sqrt(n)）。

• DFS函数：O(C(n,k))，其中C(n,k)是从n个元素中选择k个元素的组合数。

• 总时间复杂度：O(C(n,k)×sqrt（n)）。

---

5. 优化建议

• 剪枝优化：在DFS过程中，如果当前和sum已经大于某个阈值，可以提前终止递归。

• 素数预处理：如果需要多次判断素数，可以预先生成一个素数表，减少重复计算。