C语言isprime函数如何判断质数？

在C语言中,判断一个数是否为素数（质数）的函数 isprime 可以通过以下几种方式实现，以下是几种常见的方法，从简单到优化逐步介绍。

方法1：基础遍历法（效率较低）

思路：从2开始遍历到 n-1，检查是否有能整除 n 的数，如果没有，则 n 是素数。

#include <stdbool.h>
#include <math.h>
bool isprime(int n) {
    if (n <= 1) {
        return false; // 1及以下的数不是素数
    }
    for (int i = 2; i < n; i++) {
        if (n % i == 0) {
            return false; // 能整除，不是素数
        }
    }
    return true; // 遍历完无整除，是素数
}

缺点：时间复杂度为 (O(n))，当 n 很大时效率很低。

方法2：优化遍历法（推荐）

优化点：

1. 只需遍历到 (\sqrt{n})，因为如果 n 有因数，至少有一个因数 (\leq \sqrt{n})。
2. 跳过偶数（除了2），因为偶数不可能是素数（除了2）。

#include <stdbool.h>
#include <math.h>
bool isprime(int n) {
    if (n <= 1) return false;
    if (n == 2) return true;    // 2是素数
    if (n % 2 == 0) return false; // 排除偶数
    // 只需检查奇数，从3到sqrt(n)
    for (int i = 3; i <= sqrt(n); i += 2) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

时间复杂度：(O(\sqrt{n}))，比方法1高效很多。

方法3：进一步优化（预查小素数）

思路：先检查 n 是否能被小素数（如2, 3, 5, 7）整除，再进行遍历。

#include <stdbool.h>
#include <math.h>
bool isprime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;   // 2和3是素数
    if (n % 2 == 0 || n % 3 == 0) return false;
    // 检查6k±1形式的数（所有素数都符合此形式）
    for (int i = 5; i <= sqrt(n); i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) {
            return false;
        }
    }
    return true;
}

优化点：跳过更多非素数候选（如4, 6, 8等），进一步减少循环次数。

完整示例代码

#include <stdio.h>
#include <stdbool.h>
#include <math.h>
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 <= sqrt(n); i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) {
            return false;
        }
    }
    return true;
}
int main() {
    int num;
    printf("Enter a number: ");
    scanf("%d", &num);
    if (isprime(num)) {
        printf("%d is a prime number.\n", num);
    } else {
        printf("%d is not a prime number.\n", num);
    }
    return 0;
}

测试用例

• 基础方法：适用于小数字，但效率低。
• 优化方法：推荐使用，通过数学优化大幅提升性能。
• 高级优化：适用于需要处理极大数字的场景（如密码学），可能结合概率性测试（如Miller-Rabin算法）。

选择合适的方法取决于你的具体需求（如数字范围、性能要求等）。