当前位置：首页 > news >正文

方城微网站开发/培训网站官网

news 2025/7/5 20:54:32

方城微网站开发,培训网站官网,在线看免费观看视频网站大全,新疆最新疫情通报判断质数（素数）及其优化方法质数是指大于1的自然数，且只有1和它本身两个正约数。以下是几种判断方法及其优化策略。目录基础方法（试除法）优化1：仅检查到√n优化2：跳过偶数优化3&#xff…

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

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

基础方法（试除法）

检查从 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;
}