下面代码实现了欧拉（线性）筛，横线处应填写（ ）。 vector euler_sieve(int n) { vector is_composite(n + 1, false); vector primes; for (int i = 2; i <= n; i++) { if (!is_composite[i]) primes.push_back(i); for (int j = 0; j < primes.size() && (long long)i * primes[j] <= n; j++) { is_composite[i * primes[j]] = true; if (i % primes[j] == 0) break; } return primes;
A：j <= n
B：j < sqrt(n)
C：j < primes.size()
D：j < i
正确答案：C
答案解析
遍历从2开始的每个整数i，若i未被标记为合数，则将其加入素数列表。对当前素数列表中的每个素数p，标记i与p的乘积为合数，直到p能整除i时停止内层循环，确保每个合数仅被其最小的质因子筛去一次。横线处需填入控制筛法过程中最小质因子判定的变量。
试卷来源：202603 CCF-GESP编程能力等级认证C++五级真题