C语言打印1-100素数：内层for循环终止条件作用解析

以下是按练习要求、必须使用数组实现的1~100素数打印C代码：

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

int main()
{
    int p;
    int i;

    int primes[50] = {0};
    int primeIndex = 2;

    bool isPrime;

    // 硬编码初始素数
    primes[0] = 2;
    primes[1] = 3;

    for(p = 5; p <= 100; p = p + 2)
    {
        isPrime = true;

        for (i = 1; isPrime && p / primes[i] >= primes[i]; ++i)
            if (p % primes[i] == 0)
                isPrime = false;

        if (isPrime == true)
        {
            primes[primeIndex] = p;
            ++primeIndex;
        }
    }

    for ( i = 0;  i < primeIndex;  ++i )
         printf ("%i  ", primes[i]);

    printf("\n");
    return 0;
}

代码大部分逻辑可以理解，但看不懂如下循环段的设计，尤其是循环终止条件的逻辑：

for (i = 1; isPrime && p / primes[i] >= primes[i]; ++i)

条件逻辑详解 #

这个for循环是试除法找素数的核心优化点，两个终止条件分别对应不同的作用，拆开讲就很清楚：

• 第一个条件isPrime是效率剪枝：只要之前的试除已经找到能整除p的素数，就直接判定p不是素数，立刻终止循环，没必要做后续无意义的计算。
• 第二个条件p / primes[i] >= primes[i]是素数判断的经典数学优化，本质是把试除范围压缩到√p以内，完全不需要试除比√p更大的数。

为什么试除到√p就够？ #

如果数p存在大于1的因数，那因数一定是成对出现的：假设p = a * b，如果a > √p，那对应的b = p/a一定小于√p。也就是说，只要p不是素数，一定存在一个小于等于√p的因数，你只要把√p以内的数都试过没找到因数，就可以直接判定p是素数，根本不用试更大的数。

为什么用除法写而不是直接算平方根？ #

很多初学者一开始会纳闷为什么不直接写primes[i] <= sqrt(p)，这里用整数除法的写法有两个好处：

1. 避免浮点数运算的精度误差和性能开销，全是整数运算速度更快
2. 避免primes[i] * primes[i] <= p这种写法可能触发的整数溢出问题，用除法完全不会有溢出风险，适配更大范围的素数查找。

举个实际例子就好懂：比如判断p=29是不是素数，√29≈5.39，我们只需要试除≤5的素数就行：

• i=1时primes[i]=3，29/3=9（整数除法自动截断小数），9≥3成立，试除29%3≠0，继续循环
• i=2时primes[i]=5，29/5=5，5≥5成立，试除29%5≠0，继续循环
• i=3时primes[i]=7，29/7=4，4≥7不成立，循环直接终止，判定29是素数，完全不用试7、11这些更大的素数。

额外提一句，这个循环i从1开始（也就是从素数3开始试除）也是个小优化：外层循环p从5开始每次加2，遍历的全是奇数，根本不可能被2整除，所以直接跳过了primes[0]=2的试除步骤，进一步减少计算量。

内容的提问来源于stack exchange，提问作者samayspeaks