C语言递归判断素数：原理、实现与性能分析

夏知夏

发布时间：2026-10-15| 6人浏览过

原创

本文通过C语言实例讲解如何使用递归函数判断素数，对比传统试除法的优缺点。文章包含完整的递归代码实现及复杂度分析，帮助开发者理解递归在基础算法中的应用场景与局限性。

递归判断素数的核心思路

素数是只能被1和自身整除的大于1的自然数。传统的判断方法是“试除法”，即尝试用从2到$\sqrt{n}$（或$n-1$）的所有整数去除该数。若不能整除则为素数，能整除则不是。

将这一过程转化为递归函数的关键在于维护两个状态：num（待判断的数）和 divide（当前尝试除数）。递归的基本逻辑如下：

基准条件 1：如果 num 为 2，直接返回真（2是素数）。
基准条件 2：如果 divide 递减到 2，检查 num % 2 != 0。若不余数说明之前已排除偶数情况，此处主要处理边界。
递归步骤：
- 若 num % divide == 0，说明找到了因子，返回假（非素数）。
- 否则，继续递归调用 isPrime(num, divide - 1)，即将除数减 1 继续判断。

C语言代码实现

以下是基于上述逻辑的完整 C 语言实现。注意，为了简化递归深度，通常建议从 num/2 或 sqrt(num) 开始递减，但为了演示纯粹的递归概念，下面代码展示了从 num-1 开始递减的逻辑（仅作教学用途，实际生产环境不推荐）。

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

// 递归判断素数函数
int isPrime(int num, int divide) {
    // 2 是最小的素数
    if (num == 2) {
        return 1;
    }
    
    // 当除数递减到 2 时，进行最后一次检查
    if (divide == 2) {
        // 如果 num 不能被 2 整除，且之前也没被其他数整除，则是素数
        return (num % 2 != 0);
    }
    
    // 如果当前的除数能整除 num，说明不是素数
    if (num % divide == 0) {
        return 0;
    } else {
        // 否则，用更小的除数继续尝试
        return isPrime(num, divide - 1);
    }
}

int main() {
    int num;
    printf("请输入一个自然数: ");
    if (scanf("%d", &num) != 1 || num <= 0) {
        printf("输入无效，请输入大于0的整数。");
        return 1;
    }
    
    // 初始调用：待判断数为 num，尝试除数为 num - 1
    // 注意：对于大数，从 num-1 开始会导致栈溢出或极慢的效率
    int result = isPrime(num, num - 1);
    
    if (result) {
        printf("%d 是素数\n", num);
    } else {
        printf("%d 不是素数\n", num);
    }
    
    return 0;
}

效率分析与最佳实践

虽然递归写法在逻辑上实现了“试除”的过程，但在性能上存在明显劣势：

时间复杂度高：上述代码从 num-1 开始递减，最坏情况下（如输入一个大素数）需要进行 O(N) 次递归调用。而优化的迭代算法只需遍历到 sqrt(num)，复杂度为 O(√N)。
空间复杂度高：每次递归都会在调用栈中压入新的帧。深层递归可能导致栈溢出（Stack Overflow），而迭代算法的空间复杂度仅为 O(1)。