单选题
适中
#19738
下列程序实现了线性筛法(欧拉筛),用于在O(n)时间内求出1~n之间的所有质数。为了保证每个合数只被其最小质因子筛掉,横线处应填入的语句是( )。 for (…
下列程序实现了线性筛法(欧拉筛),用于在O(n)时间内求出1~n之间的所有质数。为了保证每个合数只被其最小质因子筛掉,横线处应填入的语句是( )。
答案与解析
正确答案:C
解析
遍历每个数i,若未被标记为合数,则将其加入质数列表。随后枚举已知质数primes[j],将i与primes[j]的乘积标记为合数。标记过程中,当某个质数primes[j]能整除i时,停止后续标记。因primes[j]是i的最小质因子,后续更大的质数与i相乘所得合数的最小质因子仍为primes[j],应由其他数倍增筛去。