01｜2025-03-L5-SC-05

根据唯一分解定理，下面整数的唯一分解是正确的（ ）。

{{ select(1) }}

• 18 = 3 × 6
• 28 = 4 × 7
• 36 = 2 × 3 × 6
• 30 = 2 × 3 × 5

02｜2025-06-L5-TF-01

下面C++代码是用欧几里得算法（辗转相除法）求两个正整数的最大公约数，a 大于 b 还是小于 b 都适用。

{{ select(2) }}

• 正确
• 错误

03｜2025-06-L5-SC-08

唯一分解定理描述了关于正整数的什么性质？

{{ select(3) }}

• 任何正整数都可以表示为两个素数的和。
• 任何大于1的合数都可以唯一分解为有限个质数的乘积。
• 两个正整数的最大公约数总是等于它们的最小公倍数除以它们的乘积。
• 所有素数都是奇数。

04｜2025-12-L5-SC-04

假设我们有两个数a=38和b=14，它们对模m同余，即a≡b (mod m)。以下哪个值不可能是m？

{{ select(4) }}

• 3
• 4
• 6
• 9

05｜2025-12-L5-SC-05

下面代码实现了欧几里得算法。下面有关说法，错误的是（ ）。

{{ select(5) }}

• gcd1()实现为递归方式。
• gcd2()实现为迭代方式。
• 当a较大时，gcd1()实现会多次调用自身，需要较多额外的辅助空间。
• 当a较大时，gcd1()的实现比gcd2()执行效率更高。

06｜2025-12-L5-SC-06

唯一分解定理描述的内容是（ ）。

{{ select(6) }}

• 任何正整数都可以表示为两个素数的和。
• 任何大于1的合数都可以唯一分解为有限个质数的乘积。
• 两个正整数的最大公约数总是等于它们的最小公倍数除以它们的乘积。
• 所有素数都是奇数。

07｜2026-03-L5-SC-04

对如下代码实现的欧几里得算法（辗转相除法），执行gcd(48,18)得到的调用序列为（ ）。

{{ select(7) }}

• 
• 
• 
• 

08｜2025-03-L5-TF-03

线性筛相对于埃拉托斯特尼筛法，每个合数只会被它的最小质因数筛去一次，因此效率更高。

{{ select(8) }}

• 正确
• 错误

09｜2025-03-L5-SC-04

用以下辗转相除法（欧几里得算法）求 gcd(84, 60) 的步骤中，第二步计算的数是（ ）。

{{ select(9) }}

• 84和60
• 60和24
• 24和12
• 12和0

10｜2025-06-L5-TF-02

假设函数 gcd() 函数能正确求两个正整数的最大公约数，则下面的 lcm() 函数能求相应两数的最小公倍数。

{{ select(10) }}

• 正确
• 错误

11｜2025-06-L5-TF-03

下面的C++代码用于输出每个数对应的质因数列表，输出形如：{5: [5], 6: [2, 3], 7: [7], 8: [2, 2, 2]}。

{{ select(11) }}

• 正确
• 错误

12｜2025-06-L5-SC-06

下列C++代码用两种方式求解两个正整数的最大公约数，说法错误的是（ ）。

{{ select(12) }}

• gcd0() 函数的时间复杂度为 O(log n)
• gcd1() 函数的时间复杂度为 O(n)
• 一般说来，gcd0() 的效率高于 gcd1()
• gcd1() 中的代码 for (int i = small; i >= 1; --i) 应该修改为 for (int i = small; i > 1; --i)

13｜2025-06-L5-SC-07

下面的代码用于判断一个整数是否为质数。若要找出 1 到 n 之间的所有质数，对 1 到 n 中的每个整数都调用该函数，下列说法中错误的是（ ）。

{{ select(13) }}

• 埃氏筛算法相对于上面的代码效率更高
• 线性筛算法相对于上面的代码效率更高
• 上面的代码有很多重复计算，因为不是判断单个数是否为质数，故而导致筛选出连续数中质数的效率不高
• 相对而言，埃氏筛算法比上面代码以及线性筛算法效率都高

14｜2025-09-L5-TF-01

基于下面定义的函数，通过判断 isDivisibleBy9(n) == isDigitSumDivisibleBy9(n) 代码可验算如果一个数能被9整除，则它的各位数字之和能被9整除。

{{ select(14) }}

• 正确
• 错误

15｜2025-09-L5-TF-02

假设函数 gcd() 能正确求两个正整数的最大公约数，则下面的 findMusicalPattern(4，6) 函数返回2。

{{ select(15) }}

• 正确
• 错误

16｜2025-09-L5-SC-05

以下代码计算两个正整数的最大公约数(GCD)，横线上应填写（ ）。

{{ select(16) }}

• b
• a
• temp
• a * b

17｜2025-09-L5-TF-06

线性筛关键是“每个合数只会被最小质因子筛到一次”，因此为 O(n)。

{{ select(17) }}

• 正确
• 错误

18｜2025-09-L5-SC-08

关于埃氏筛和线性筛的比较，下列说法错误的是（ ）。

{{ select(18) }}

• 埃氏筛可能会对同一个合数进行多次标记
• 线性筛的理论时间复杂度更优，所以线性筛的速度往往优于埃氏筛
• 线性筛保证每个合数只被其最小质因子筛到一次
• 对于常见范围（n ≤ 10⁷），埃氏筛因实现简单，常数较小，其速度往往优于线性筛

19｜2025-09-L5-SC-09

唯一分解定理描述的是( )。

{{ select(19) }}

• 每个整数都能表示为任意素数的乘积
• 每个大于 1 的整数能唯一分解为素数幂乘积（忽略顺序）
• 合数不能分解为素数乘积
• 素数只有两个因子：1 和自身

20｜2025-12-L5-TF-02

假设函数gcd()函数能正确求两个正整数的最大公约数，则下面的lcm(a，b)函数能正确找到两个正整数a和b的最小公倍数。

{{ select(20) }}

• 正确
• 错误

21｜2025-12-L5-TF-04

在求解所有不大于n的素数时，线性筛法（欧拉筛）都应当优先于埃氏筛法使用，因为线性筛法的时间复杂度为O(n)，低于埃氏筛法的O(n log log n)。

{{ select(21) }}

• 正确
• 错误

22｜2026-03-L5-SC-05

下面代码实现了欧拉（线性）筛，横线处应填写（ ）。

{{ select(22) }}

• 
• 
• 
• 

23｜2026-03-L5-SC-06

埃氏筛中将内层循环从j=i*i开始而不是j=2*i的主要原因是（ ）。

{{ select(23) }}

• 因为2*i一定不是合数
• i*i一定是质数
• 小于i*i的i的倍数已被更小质因子筛过
• 这样可以把时间复杂度降为O(n)

24｜2026-03-L5-TF-06

根据唯一分解定理，如果大于1的n不被任何不超其平方根的质数整除，则n是质数。

{{ select(24) }}

• 正确
• 错误

25｜2026-03-L5-TF-09

线性筛相比埃氏筛的核心改进在于：埃氏筛中一个合数可能被多个质数重复标记，线性筛通过“每个合数只被其最大质因子筛去”的策略，保证每个合数恰好被标记一次，从而实现O(n)的时间复杂度。

{{ select(25) }}

• 正确
• 错误

26｜2026-06-L5-TF-03

对任意正整数 a、b，以下两种写法的 gcd 函数返回值完全相同。

{{ select(26) }}

• 正确
• 错误

27｜2026-06-L5-SC-04

使用如下欧几里得算法求 gcd(105, 45) 时，函数 gcd(a, b) 的递归调用序列正确的是（ ）。

{{ select(27) }}

• gcd(105, 45) -> gcd(45, 60) -> gcd(60, 15) -> gcd(15, 0)
• gcd(105, 45) -> gcd(45, 15) -> gcd(15, 0)
• gcd(105, 45) -> gcd(60, 45) -> gcd(15, 45)
• gcd(105, 45) -> gcd(15, 45) -> gcd(15, 0)

28｜2026-06-L5-SC-06

下面关于埃氏筛法的说法正确的是（ ）。

{{ select(28) }}

• 每个合数只会被筛掉一次
• 从每个素数出发，把它的倍数标记为合数
• 只能判断一个数是不是偶数
• 不能求出素数表

29｜2026-06-L5-SC-08

下面代码用于统计 n 中因子 2 出现了多少次。若 n = 40，输出是（ ）。

{{ select(29) }}

• 1
• 2
• 3
• 4

30｜2026-06-L5-TF-09

唯一分解定理表明，任何一个大于 1 的自然数都可以唯一地分解为若干个质数的乘积，如果不考虑质因数的顺序，这种分解方式是唯一的。

{{ select(30) }}

• 正确
• 错误

31｜2025-03-L5-SC-06

下述代码实现素数表的线性筛法，筛选出所有小于等于 n 的素数，横线上应填的最佳代码是（ ）。

{{ select(31) }}

• j < primes.size()
• i * primes[j] <= n
• j < primes.size() && i * primes[j] <= n
• j <= n

32｜2025-06-L5-SC-05

下列C++代码判断一个正整数是否是质数，说法正确的是（ ）。

{{ select(32) }}

• 代码存在错误，比如5是质数，但因为 5 % 5 余数是0返回了 false
• finish_number 的值应该是 n / 2，当前写法将导致错误
• 当前 while 循环正确的前提是：所有大于3的质数都符合 6k±1 形式
• 

33｜2025-06-L5-TF-10

如下为线性筛法，用于高效生成素数表，其核心思想是每个合数只被它的最小质因数筛掉一次，时间复杂度为 O(n)。

{{ select(33) }}

• 正确
• 错误

34｜2025-09-L5-SC-04

函数 isPerfectNumber 判断一个正整数是否为完全数（该数是否即等于它的真因子之和），则横线上应填写（ ）。一个正整数 n 的真因子包括所有小于 n 的正因子，如28的真因子为1, 2, 4, 7, 14。

{{ select(34) }}

• i <= n
• i*i <= n
• i <= n/2
• i < n

35｜2025-09-L5-SC-06

函数 sieve 实现埃拉托斯特尼筛法(埃氏筛)，横线处应填入（ ）。

{{ select(35) }}

• i
• i+1
• i*2
• i*i

36｜2025-09-L5-SC-07

函数 linearSieve 实现线性筛法(欧拉筛)，横线处应填入（ ）。

{{ select(36) }}

• i % p == 0
• p % i == 0
• i == p
• i * p == n

37｜2025-12-L5-SC-07

下述代码实现素数表的线性筛法，筛选出所有小于等于n的素数，则横线上应填的代码是（ ）。

{{ select(37) }}

• for (int j = 0; j < primes.size() && i * primes[j] <= n; j++)
• for(int j = sqrt(n); j <= n && i * primes[j] <= n; j++)
• for (int j = 1; j <= sqrt(n); j++)
• for(int j = 1; j < n && i * primes[j] <= n; j++)

38｜2026-06-L5-SC-05

下面代码实现线性筛（欧拉筛），以筛选出 n 以内的所有素数。横线处的代码应为（ ）。

{{ select(38) }}

• i % primes[j] == 0
• primes[j] % i == 0
• i % primes[j] != 0
• i == primes[j]