C语言高效统计100以内素数个数的方法与代码实现

月亮慢半拍

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

原创

介绍如何利用C语言基础语法结合数学知识，高效统计100以内的素数个数，并通过引入平方根算法提升运行速度。

结果与目标

C语言编程中，基础的数据处理与逻辑判断是核心能力。通过统计特定范围内（如100以内）的素数个数，不仅可以掌握循环结构、条件分支的使用方法，还能直观体会到算法优化对程序性能的提升。最终目标是得到一个准确且高效的计数程序。

准备条件

开发环境：标准 C 编译器（支持 C99 及以上标准）。
核心概念：素数（质数）是指大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的数。例如：2、3、5、7 等。
依赖头文件：用于基础输入输出的 stdio.h 以及用于数学运算函数的 math.h。

操作顺序

第1步：理解基础循环与判断逻辑

首先确定我们需要遍历的范围。因为 1 不是素数，最小的素数是 2，所以循环变量应从 2 开始遍历到 100。对于范围内的每一个数字，都需要调用一个判断函数来检测其是否为素数。

#include <stdio.h>

#define INTEGER_RANGE 100  //数字范围

int if_prime(int num);

int main()
{
    int sum = 0;
    /* 2是最小的素数，for循环范围为2-100 */
    for(int i = 2; i <= INTEGER_RANGE; i++)
    {
        if(if_prime(i))
            sum++;
    }
    printf("%d以内的素数个数为：%d\n", INTEGER_RANGE, sum);
    return 0;
}

/*
 * 判断是否为素数，是则返回1，否返回0
 * */
int if_prime(int num)
{
    int i = 0;
    for(i = 2; i < num; i++)
    {
        /* 如果该数有存在1以外的其他正因数，则不是素数 */
        if(num % i == 0)
            return 0;
    }
    return 1;
}

第2步：查看基础运行效果

编译并运行上述代码后，控制台应输出 100 以内素数的总数量。此步骤验证了基本逻辑的正确性。

第3步：应用数学库优化算法（进阶）

在第一步的基础版代码中，判断素数的循环会一直持续到 num - 1。事实上，当合数 $m$ 可以分解为 $a \times b = m$ 时，若设定 $a \le b$，则必然有 $a \le \sqrt{m}$。这意味着如果在 2~sqrt(num) 范围内没有发现因数，则该数必定为素数。这一改进可大幅减少循环次数，提升性能。

增加边界检查：if (num < 2) return 0;，确保输入小于 2 的数字直接返回假。
缩小循环范围：将内层循环终止条件由 i < num 改为 i <= sqrt(num)。

以下是经过优化的完整 if_prime 函数实现：

#include <math.h>

/*
 * 判断是否为素数，是则返回1，否返回0（改进版）
 * */
int if_prime(int num)
{
    if(num < 2)
        return 0; //最小的素数为2
    
    int i = 0;
    //sqrt():开方函数（一定要写小于等于）
    for(i = 2; i <= sqrt(num); i++)
    {
        /* 如果该数有存在1以外的其他正因数，则不是素数 */
        if(num % i == 0)
            return 0;
    }
    return 1;
}

第4步：验证综合逻辑

参考网上优秀的解题思路，还可以采用另一种常见的写法，即在主循环中先计算平方根存为临时变量，再进行判断，这在实际工程中非常实用：

//  Created by www.runoob.com on 15/11/9.
//  Copyright © 2015年 菜鸟教程. All rights reserved.
//
 
#include<stdio.h>
#include<math.h>

int main()
{
    int i, j, k, n = 0;
    for(i = 2; i <= 100; i++)
    {
        k = (int)sqrt(i);
        for(j = 2; j <= k; j++)
            if(i % j == 0) break;
        if(j > k)
        {
            printf("%d ", i);
            n++;
            if(n % 5 == 0)
                printf("\n");
        }
    }
    return 0;
}