C语言判断质数：优化算法与函数实现指南

Hazel

发布时间：2026-10-16| 3人浏览过

原创

在C语言编程中，判断一个整数是否为质数（素数）是基础且常见的任务。本文将深入剖析判断质数的关键逻辑，包括边界条件的处理和循环效率的优化，并提供经过验证的正确函数实现，解决常见误判问题。

核心逻辑与边界条件

编写判断质数的程序时，必须严谨地处理三个关键环节：

起始边界： 2 是最小的质数，也是唯一的偶数质数，需单独考虑，不进入后续循环。
循环主体与优化： 除数从 2 开始递增。为了提升效率，除数可以仅遍历奇数或使用特定的步进方式。例如，代码中使用的 divisor += (divisor % 2 + 1) 逻辑可实现快速跳过非必要的检查项。
结束条件： 当循环执行到接近目标数值时，若仍未发现能整除的因子，则可判定为质数。具体而言，当 divisor 达到 n-1 或 n-2 时，若此前未中断，则确认 n 为质数。

基础实现代码

以下是基于上述逻辑的基础实现。注意输入值 n 通过标准输入获取，并根据结果输出 YES 或 NO：

#include <stdio.h>
int main() {
    int divisor;
    int n;
    scanf("%d",&n); // 输入要判断的数
    if (n == 2) {
        printf("YES"); 
    } else {
        for (divisor = 2; divisor < n; divisor += (divisor % 2 + 1) ) {
            if (n % divisor == 0) {
                printf("NO"); // 当出现能被1或自身之外整除时
                break;
            } else if (divisor == n - 1 || divisor == n-2) {
                printf("YES"); // 循环到 n-1 或 n-2 时，仍然没有被其他数整除
            }
        }
    }
    return 0;
}

封装为独立函数的最佳实践

为了代码复用性和清晰度，通常将判断逻辑封装为 prime 函数。在实际开发中，初学者编写的版本往往存在漏洞，例如未能正确排除 0 和 1，或者在循环条件上出现偏差。

常见错误分析

若直接调用函数而不处理 n <= 1 的情况，程序可能会误判。此外，循环的上限应严格控制在 n/2 以内，因为大于 n/2 的数（除了 n 本身）不可能整除 n。

修正后的完整代码

以下代码经过修正，能够正确处理负数、0、1 以及正常的合数和质数情况：

#include <stdio.h> 
int main()
   {
    int prime(int);//函数声明
    int n;
    printf("请输入一个整数：\n");
    scanf("%d",&n);	
    if(prime(n))
	{    
        printf("%d 是素数。\n",n);
    }else
    {
        printf("%d 不是素数。\n",n);
    }
    return 0;
   }
int prime(int n)  //函数定义
{
    int flag = 1,i;
    // 首先排除小于等于1的非质数
    if (n <= 1)  
       flag = 0; 
    else {
        // 从2开始遍历到n/2
        for(i=2;i <= n/2 && flag == 1;i++) 
            if (n%i == 0)                 // 如果能被整除，则不是素数
            flag=0;                     // 标记为非素数
    }
    return flag;
}