埃氏筛中将内层循环从 j = i*i 开始而不是 j = 2*i 的主要原因是（ ）。 vector eratosthenes_sieve(int n) { vector is_composite(n + 1, false); vector primes; for (int i = 2; i <= n; i++) { if (is_composite[i]) continue; primes.push_back(i); for (long long j = (long long)i * i; j <= n; j += i) is_composite[j] = true; } return primes;
A：因为 2*i 一定不是合数
B：i*i 一定是质数
C：小于 i*i 的 i 的倍数已被更小质因子筛过
D：这样可以把时间复杂度降为O（n）
正确答案：C
答案解析
在埃氏筛法中，对于当前质数i，需要标记其倍数为合数。内层循环从j = i*i开始，是因为所有小于i*i且为i的倍数的数，必定存在一个比i小的因子，因此这些数已经被之前更小的质数筛除。从i*i开始可以避免重复标记，确保每个合数仅在其最小质因子被处理时被筛去。该起始点选择不影响最终结果，但优化了执行效率，减少了冗余操作。循环起始位置与时间复杂度渐进行为无本质关联，也不依赖特定数值的质合属性。
试卷来源：202603 CCF-GESP编程能力等级认证C++五级真题