软件定制价格_软件开发培训机构学费_广州网络营销选择_巩义关键词优化推广

判断质数（素数）及其优化方法

质数是指 大于1的自然数，且 只有1和它本身两个正约数。以下是几种判断方法及其优化策略。

---

目录

1. 基础方法（试除法）
2. 优化1：仅检查到√n
3. 优化2：跳过偶数
4. 优化3：6k±1法则
5. 优化4：筛法预处理
6. 方法对比总结

基础方法（试除法）

检查从 2 到 n-1 的所有整数，若存在能整除 n 的数，则 n 不是质数。

代码实现

bool isPrime(int n) {if (n <= 1) return false;for (int i = 2; i < n; i++) {if (n % i == 0) return false;}return true;
}

最简单直接的方法，时间复杂度：O(n)，仅适用于学习，实际效率低

优化1：仅检查到√n

数学原理
若n不是质数，则必有一个因数≤√n

bool isPrimeSqrt(int n) {if (n <= 1) return false;for (int i = 2; i * i <= n; i++) {if (n % i == 0) return false;}return true;
}

时间复杂度：O(√n)，最常用的单次判断方法

优化2：跳过偶数

除了 2，所有偶数都不是质数，因此可以跳过所有偶数。

bool isPrime(int n) {if (n <= 1) return false;if (n == 2) return true;      // 2 是质数if (n % 2 == 0) return false; // 排除所有偶数for (int i = 3; i * i <= n; i += 2) { // 只检查奇数if (n % i == 0) {return false;}}return true;
}

时间复杂度：O(√n/2)

方法4：6k±1法则（高级优化）

bool isPrime(int n) {if (n <= 1) return false;if (n <= 3) return true;if (n % 2 == 0 || n % 3 == 0) return false;for (int i = 5; i * i <= n; i += 6) {if (n % i == 0 || n % (i + 2) == 0) return false;}return true;
}

基于数学定理：质数呈6k±1分布，时间复杂度：O(√n/3)，最高效的单次判断方法

方法5：筛法预处理（适合多次查询）

#include <vector>
using namespace std;vector<bool> sieve(int max_num) 
{vector<bool> is_prime(max_num + 1, true);is_prime[0] = is_prime[1] = false;for (int i = 2; i * i <= max_num; i++)  {if (is_prime[i]) {for (int j = i * i; j <= max_num; j += i) //i如果是质数，那么i*i就肯定不是质数{is_prime[j] = false;}}}return is_prime;
}int main() {int max_num = 100;vector<bool> is_prime = sieve(max_num); //调用sieve得到一个标记了质数的数组，可以用O(1)的时间复杂度判断一个数是否为质数int num = 17;cout << num << (is_prime[num] ? " 是质数" : " 不是质数") << endl;return 0;
}

筛法中为什么要标记i*i而不是i*2或者i*3

关键推论：当处理到质数i时：i*2, i*3,..., i*(i-1)都已被更小的质数标记过（避免重复标记）

举例说明：

以n=30为例，标记过程对比：
从i*i开始的标记顺序：
i=2: 4,6,8,10,12,14,16,18,20,22,24,26,28,30
i=3: 9,15,21,27
i=5: 25
（共标记14次）

从i*2开始的标记顺序：
i=2: 4,6,8,…,30
i=3: 6,9,12,…,30（其中6,12,18…已标记）
i=5: 10,15,20,25,30（其中10,15,20,30已标记）
（共标记25次，其中11次是重复的）

当n=1,000,000时：
优化版：约执行800,000次标记
非优化版：约执行1,500,000次标记
（节省近50%的操作）