C语言素数生成示例代码核心逻辑解析求助

这段代码的作用是生成50以内的全部素数，采用了试除法的优化实现，你标注的核心判断部分是素数校验的核心逻辑，拆解如下：

前置说明 #

• 代码提前将最小的两个素数2、3存入primes数组，后续只遍历大于3的奇数（从5开始每次加2），因为所有偶数除了2都不可能是素数，省去了一半无效校验
• isPrime是布尔标记位，默认假设当前校验的数p是素数，只要找到任意一个能整除p的数，就会被标记为非素数
• primes数组按从小到大顺序存储已经确认的素数，校验p时只会用比p小的已存素数试除

核心代码逐段拆解 #

你标注的核心代码如下：

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

for循环参数拆解 #

1. 初始值i = 1：因为当前校验的p都是奇数，不可能被primes[0]也就是2整除，所以直接跳过2，从第一个奇素数3（对应索引1）开始试除，减少无效计算
2. 循环继续条件有两个，同时满足才会执行循环体：
   • isPrime：只要之前的试除已经找到p的因数，标记为非素数，就直接终止循环，不需要继续校验
   • p / primes[i] >= primes[i]：等价于数学上的p >= primes[i]²，也就是校验的素数只需要到√p为止。如果p存在大于√p的因数，那对应的另一个因数一定小于√p，早就已经被校验过了，不需要再往后试，这里用除法代替乘法是为了避免大整数相乘溢出，属于通用写法
3. 迭代逻辑++i：每次循环结束后，取下一个已确认的素数继续试除

循环体逻辑 #

if (p % primes[i] == 0)是判断当前试除的素数primes[i]能否整除p，如果余数为0，说明p存在除了1和自身之外的因数，不是素数，直接将isPrime设为false。

示例运行验证 #

举两个实际运行的例子帮你理解：

• 当p=5时：初始i=1，primes[1]=3，5/3=1，1 >= 3不成立，循环直接不执行，isPrime保持true，所以5是素数，存入数组
• 当p=25时：初始i=1，primes[1]=3，25/3=8 >=3成立，25%3=1不满足整除条件，i变成2；下一轮循环primes[2]=5，25/5=5 >=5成立，25%5=0，将isPrime设为false，循环终止，25不是素数，不会存入数组

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