C语言实现素数判断算法与优化技巧

1. 素数计算的基本原理与算法设计

素数（质数）是只能被1和它本身整除的自然数。在计算机编程中，判断一个数是否为素数是一个经典的基础算法问题。我们先从数学角度理解素数的定义和判断方法。

数学上判断素数最直接的方法是试除法：对于一个待判断的数n，用2到√n之间的所有整数去除n。如果都不能整除，则n是素数。这是因为如果n有大于√n的因数，那么它必然对应一个小于√n的因数，所以只需要检查到√n即可。

在C语言实现中，我们需要考虑以下几个关键点：

1. 外层循环控制数字范围（100-200）
2. 内层循环进行素数判断（2到√i）
3. 使用标志变量记录判断结果
4. 优化判断范围（只需判断到√i而非i-1）

注意：实际编程中判断到√i而不是i-1可以显著提高效率，特别是处理大数时。例如判断197是否为素数，只需检查2到14之间的整数即可（√197≈14）。

2. 基础实现代码解析

让我们先分析提供的原始代码，理解其工作原理：

c复制#include<stdio.h>
int main() {
    for (int i = 100; i < 200; i++) {
        int j = 1; // 假设定义j=1时是素数
        for (int m = 2; m < i; m++) {
            if (i % m == 0) {
                j = 0; // j=0表示不是素数
                break;
            }
        }
        if (j == 1) // 只有j=1时才打印素数
        {
            printf("%d  ", i);
        }
    }
    return 0;
}

这段代码的工作流程：

1. 外层for循环遍历100到199的所有整数
2. 初始化标志变量j为1（假设当前数字i是素数）
3. 内层for循环用2到i-1的所有整数测试是否能整除i
4. 如果发现能整除的数，设置j=0并跳出内层循环
5. 循环结束后检查j的值，如果仍为1则打印该素数

这个实现虽然正确，但存在可以优化的空间。主要问题是内层循环的判断范围过大（到i-1），实际上只需要判断到