素数筛法与唯一分解定理（共 20 题）

单选题

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

   vector<int> euler_sieve(int n) {
       vector<bool> is_composite(n + 1, false);
       vector<int> primes;
       for (int i = 2; i <= n; i++) {
           if (!is_composite[i]) primes.push_back(i);
           for (int j = 0; __________________; j++) {
               is_composite[i * primes[j]] = true;
               if (i % primes[j] == 0) break;
           }
       }
       return primes;
   }
   

   {{ select(1) }}

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

2. 埃氏筛中将内层循环从 j = ii 开始而不是 j = 2i 的主要原因是（ ）。
   {{ select(2) }}

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

3. 唯一分解定理描述的内容是（ ）。
   {{ select(3) }}

• 任意整数都可以分解为素数的乘积
• 每个合数都可以唯一分解为一系列素数的乘积
• 两个不同的整数可以分解为相同的素数乘积
• 以上都不对

4. 下面的代码用于判断整数 n 是否是质数，错误的说法是（ ）。

   bool is_prime(int n) {
       if (n <= 1) return false;
       int finish_number = static_cast<int>(sqrt(n)) + 1;
       for (int i = 2; i < finish_number; ++i) {
           if (n % i == 0) return false;
       }
       return true;
   }
   

   {{ select(4) }}

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

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

   vector<int> linear_sieve(int n) {
       vector<bool> is_prime(n + 1, true);
       vector<int> primes;
       is_prime[0] = is_prime[1] = false;
       for (int i = 2; i <= n; ++i) {
           if (is_prime[i]) primes.push_back(i);
           for (int j = 0; __________________; ++j) {
               is_prime[i * primes[j]] = false;
               if (i % primes[j] == 0) break;
           }
       }
       return primes;
   }
   

   {{ select(5) }}

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

6. 关于埃氏筛和线性筛的比较，下列说法错误的是（ ）。
   {{ select(6) }}

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

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

   vector<int> linear_sieve(int n) {
       vector<bool> is_prime(n + 1, true);
       vector<int> primes;
       for (int i = 2; i <= n; ++i) {
           if (is_prime[i]) primes.push_back(i);
           for (int p : primes) {
               if (p * i > n) break;
               is_prime[p * i] = false;
               if (__________________) break;
           }
       }
       return primes;
   }
   

   {{ select(7) }}

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

8. 素数的线性筛法时间复杂度为（ ）。
   {{ select(8) }}

• O(n)
• O(n log log n)
• O(n log n)
• O(n²)

9. 在埃拉托斯特尼筛法中，要筛选出不大于 n 的所有素数，最外层循环应该遍历什么范围（ ）。
   {{ select(9) }}

• for (int i = 2; i <= n; ++i)
• for (int i = 1; i < n; ++i)
• for (int i = 2; i <= sqrt(n); ++i)
• for (int i = 1; i <= sqrt(n); ++i)

10. 根据唯一分解定理，下面整数的唯一分解正确的是（ ）。
    {{ select(10) }}

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

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

    vector<int> euler_sieve(int n) {
        vector<bool> is_composite(n + 1, false);
        vector<int> primes;
        for (int i = 2; i <= n; i++) {
            if (!is_composite[i]) primes.push_back(i);
            for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) {
                is_composite[i * primes[j]] = true;
                if (__________________) break;
            }
        }
        return primes;
    }
    

    {{ select(11) }}

• i % primes[j] == 0
• primes[j] % i == 0
• i == primes[j]
• i * primes[j] == n

12. 唯一分解定理表明，每个大于1的自然数可以唯一地写成若干个质数的乘积。下面函数将自然数 n 的所有质因数找出来，横线上能填写的最佳代码是（ ）。

    vector<int> get_prime_factors(int n) {
        vector<int> factors;
        while (n % 2 == 0) { factors.push_back(2); n /= 2; }
        for (int i = 3; __________________; i += 2) {
            while (n % i == 0) { factors.push_back(i); n /= i; }
        }
        if (n > 2) factors.push_back(n);
        return factors;
    }
    

    {{ select(12) }}

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

13. 下述代码实现素数表的埃拉托斯特尼筛法，筛选出所有小于等于 n 的素数，则横线上应填的最佳代码是（ ）。

    void sieve_Eratosthenes(int n) {
        vector<bool> is_prime(n + 1, true);
        vector<int> primes;
        for (int i = 2; i * i <= n; i++) {
            if (is_prime[i]) {
                primes.push_back(i);
                for (int j = __________________; j <= n; j += i)
                    is_prime[j] = false;
            }
        }
        for (int i = sqrt(n) + 1; i <= n; i++) {
            if (is_prime[i]) primes.push_back(i);
        }
        return primes;
    }
    

    {{ select(13) }}

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

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

    vector<int> linear_sieve(int n) {
        vector<bool> is_prime(n + 1, true);
        vector<int> primes;
        for (int i = 2; i <= n / 2; i++) {
            if (is_prime[i]) primes.push_back(i);
            for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) {
                is_prime[i * primes[j]] = false;
                if (i % primes[j] == 0) break;
            }
        }
        for (int i = n / 2 + 1; i <= n; i++) {
            if (is_prime[i]) primes.push_back(i);
        }
        return primes;
    }
    

    下面说法，正确的是（ ）。
    {{ select(14) }}

• 线性筛的时间复杂度是 O(n)
• 每个合数会被其所有的质因子标记一次
• 线性筛和埃拉托色尼筛的实现思路完全相同
• 以上都不对

15. 下面代码实现素数表的埃拉托色尼(埃氏)筛法，筛选出所有小于等于 n 的素数。下面说法，正确的是（ ）。

    vector<int> sieve_Eratosthenes(int n) {
        vector<bool> is_prime(n + 1, true);
        vector<int> primes;
        for (int i = 2; i * i <= n; i++) {
            if (is_prime[i]) {
                primes.push_back(i);
                for (int j = i * i; j <= n; j += i) {
                    is_prime[j] = false;
                }
            }
        }
        for (int i = sqrt(n) + 1; i <= n; i++) {
            if (is_prime[i]) primes.push_back(i);
        }
        return primes;
    }
    

    {{ select(15) }}

• 代码的时间复杂度是 O(n√n)
• 在标记非素数时，代码从 i² 开始，可以减少重复标记
• 代码会输出所有小于等于 n 的奇数
• 调用函数 sieve_Eratosthenes(10)，函数返回值的数组中包含的元素有：2，3，5，7，9

判断题

16. 根据唯一分解定理，如果大于 1 的整数不能被任何不超过其平方根的质数整除，那么 n 必定是质数。
    {{ select(16) }}

• 正确
• 错误

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

• 正确
• 错误

18. 找出自然数 n 以内的所有质数，常用算法有埃拉托斯特尼（埃氏）筛法和线性筛法，其中线性筛法效率更高。
    {{ select(18) }}

• 正确
• 错误

19. 素数表的埃氏筛法和线性筛法的时间复杂度都是 O(n log log n)。
    {{ select(19) }}

• 正确
• 错误

20. 唯一分解定理表明任何一个大于 1 的整数都可以唯一地分解为素数之和。
    {{ select(20) }}

• 正确
• 错误