用c语言怎么判断素数

素数也叫质数，是大于1的自然数中，除了1和它自身外，不能被其他自然数整除的数。用C语言判断一个数是否为素数，核心逻辑就是验证该数是否存在除了1和自身之外的其他因数。

基础判断方法实现

最基础的判断思路是：对于输入的大于1的整数n，从2开始到n-1依次遍历，检查是否存在能整除n的数。如果存在这样的数，说明n不是素数；如果遍历完都没有找到，说明n是素数。

需要注意两个特殊情况：小于等于1的数不是素数，2是最小的素数也是唯一的偶素数。

下面是基础方法的C语言实现代码：

#include <stdio.h>

// 判断素数的函数，返回1表示是素数，返回0表示不是素数
int isPrime(int n) {
    // 小于等于1的数不是素数
    if (n <= 1) {
        return 0;
    }
    // 从2遍历到n-1
    for (int i = 2; i < n; i++) {
        // 如果存在能整除n的数，不是素数
        if (n % i == 0) {
            return 0;
        }
    }
    // 遍历完都没有找到因数，是素数
    return 1;
}

int main() {
    int num;
    printf("请输入一个整数：");
    scanf("%d", &num);
    if (isPrime(num)) {
        printf("%d是素数n", num);
    } else {
        printf("%d不是素数n", num);
    }
    return 0;
}

优化判断方法

基础方法的时间复杂度是O(n)，当n的值很大时，判断效率会比较低。其实我们不需要遍历到n-1，只需要遍历到sqrt(n)（n的平方根）就可以完成判断。

原因是如果n存在大于sqrt(n)的因数，那么必然存在对应的小于sqrt(n)的因数，两者相乘等于n。所以只需要检查2到sqrt(n)之间的数是否能整除n即可，这样可以减少大量的循环次数，优化后的时间复杂度是O(sqrt(n))。

优化方法的实现代码如下：

#include <stdio.h>
#include <math.h>

// 优化后的素数判断函数
int isPrimeOptimized(int n) {
    // 小于等于1的数不是素数
    if (n <= 1) {
        return 0;
    }
    // 2是素数
    if (n == 2) {
        return 1;
    }
    // 大于2的偶数不是素数
    if (n % 2 == 0) {
        return 0;
    }
    // 只需要遍历到sqrt(n)，且只需要检查奇数
    int limit = (int)sqrt(n);
    for (int i = 3; i <= limit; i += 2) {
        if (n % i == 0) {
            return 0;
        }
    }
    return 1;
}

int main() {
    int num;
    printf("请输入一个整数：");
    scanf("%d", &num);
    if (isPrimeOptimized(num)) {
        printf("%d是素数n", num);
    } else {
        printf("%d不是素数n", num);
    }
    return 0;
}

两种方法的对比

我们可以通过一个简单的对比来看两种方法的效率差异：

在实际编程中，如果只需要判断较小的数，基础方法已经足够使用；如果需要处理较大的数值或者需要批量判断素数，推荐使用优化后的方法。

常见注意事项

• 输入为1或者负数时，要直接返回不是素数，避免逻辑错误
• 使用平方根优化时，需要包含math.h头文件，编译时可能需要添加-lm参数链接数学库
• 判断循环的条件是i <= limit，不要漏掉等于的情况，否则可能会错误判断完全平方数是否为素数
• 可以先判断偶数，减少后续的循环次数，进一步提升效率

C语言素数判断算法实现循环结构修改时间：2026-07-13 23:00:12