单选题
适中
#24783
埃氏筛中将内层循环从 j = i*i 开始而不是 j = 2*i 的主要原因是( )。 vector<int> eratosthenes_sieve(int n…
埃氏筛中将内层循环从 j = i*i 开始而不是 j = 2*i 的主要原因是( )。
vector<int> eratosthenes_sieve(int n) {
vector<bool> is_composite(n + 1, false);
vector<int> 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;
}
答案与解析
正确答案:C
解析
在埃氏筛法中,对于当前质数i,需要标记其倍数为合数。内层循环从j = i*i开始,是因为所有小于i*i且为i的倍数的数,必定存在一个比i小的因子,因此这些数已经被之前更小的质数筛除。从i*i开始可以避免重复标记,确保每个合数仅在其最小质因子被处理时被筛去。该起始点选择不影响最终结果,但优化了执行效率,减少了冗余操作。循环起始位置与时间复杂度渐进行为无本质关联,也不依赖特定数值的质合属性。