A22096. $下列程序实现了线性筛法(欧拉筛)，用于在O(n)时间内求出1~n之间的所有质数。为了保证每个合数只被其最小质因子筛掉，横线处应填入的语句是（）。for (int i= 2; i<= n; i++){ if (lnot_prime[i]) primes[++cnt] = i; for (int j= 1; j<= cnt && i primes[j]<= n; j++) { not_prime[…$

单选题困难

知识点

线性筛法质数筛法循环结构

题目描述

下列程序实现了线性筛法(欧拉筛)，用于在O(n)时间内求出1~n之间的所有质数。为了保证每个合数只被其最小质因子筛掉，横线处应填入的语句是（    ）。for (int i= 2; i<= n; i++){ if (lnot_prime[i]) primes[++cnt] = i; for (int j= 1; j<= cnt && i primes[j]<= n; j++) { not_prime[i* primes[j]] = true; if(______________)break;//在此处填入选项 } }

i+ primes[j] == n

primes[j] > i

i % primes[j] == 0

i% primes[j] != 0

上一题下一题