C++素数数组代码中sqrt循环筛选素数及判断9为合数的原理咨询

1. 核心素数判定规则解析 #

你提到的isprime = trial % primes[i] > 0是素数判定的核心逻辑，原理如下：

• 素数的定义是大于1的自然数，除了1和自身外没有其他正因数。如果待检测的数trial能被任意更小的素数整除，就说明它是合数。
• 模运算符%返回两个数相除的余数，余数为0代表可以整除。所以当trial % primes[i] == 0时，trial % primes[i] > 0的结果为false，赋值给isprime后直接标记当前待检测数为合数。
• for循环内置了&& isprime的判断，一旦isprime变为false，会立刻终止循环，不需要继续检测后续素数，提升运行效率。

2. limit变量（sqrt(trial)）的作用 #

这里用到了基础的数论结论：如果n是合数，那么它必然存在一个小于等于√n的正因数。
推导逻辑：假设合数n可以拆分为ab（a和b都是大于1的正整数），如果a和b都大于√n，那么ab > √n * √n =n，和n=a*b矛盾。所以我们只需要检测所有小于等于√n的素数，就能确定n是不是素数，不需要检测到n-1，大幅减少了计算量。

3. 代码识别9为合数的完整流程 #

我们可以模拟trial=9时的运行步骤，直观看到判定逻辑：

1. 此时primes数组已经存储了前两个素数：primes[0]=2，primes[1]=3，count=2
2. 计算limit = static_cast(sqrt(9)) = 3
3. 初始化isprime为true，进入for循环：
   • i=0时，primes[0]=2 ≤3，isprime为true。计算9%2=1>0，isprime保持true
   • i=1时，primes[1]=3 ≤3，isprime为true。计算9%3=0，0>0的结果为false，isprime赋值为false
   • 下一轮循环先判断条件，isprime已经为false，直接终止循环
4. 因为isprime为false，9不会被存入素数数组，trial加2变为11，进入下一轮检测

额外优化点说明 #

代码里还有几个隐藏的优化设计：

• 初始种子素数设为2，待检测数trial从3开始每次加2，直接跳过所有偶数，因为大于2的偶数都不是素数，减少了一半的检测量
• 只用已经找到的素数做除数检测，不需要用所有整数，因为合数的因数必然包含素数，进一步减少了计算量

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