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

判断质数及其优化方法

article 2025/4/2 20:27:01

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

质数是指 大于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;
}