GESP 5级客观题｜素数、筛法与唯一分解｜课后作业

考试频率：高频。本卷共 6 题。

1. 下述代码实现素数表的线性筛法，筛选出所有⼩于等于 n 的素数，则横线上应填的代码是( )。

vector<int> sieve_linear(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);
        ________________________________ {    // 在此处填入代码
            is_prime[i * primes[j]] = 0;
            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(1) }}

• for (int j = 0; j < primes.size() && i * primes[j] <= n; j++)
• for (int j = 1; j < primes.size() && i * j <= n; j++)
• for (int j = 2; j < primes.size() && i * primes[j] <= n; j++)
• 以上都不对

2. 找出⾃然数 $n$ 以内的所有质数，常⽤算法有埃拉托斯特尼（埃⽒）筛法和线性筛法，其中线性筛法效率更⾼。

   {{ select(2) }}

• 对
• 错

3. 唯一分解定理描述的内容是（ ）？

   {{ select(3) }}

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

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

vector<int> sieveOfEratosthenes(int n) {
    std::vector<bool> isPrime(n + 1, true);
    std::vector<int> primes;
    _______________________ {
        if (isPrime[i]) {
            primes.push_back(i);
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    for (int i = sqrt(n) + 1; i <= n; ++i) {
        if (isPrime[i]) {
            primes.push_back(i);
        }
    }
    return primes;
}

{{ select(4) }}

• 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)

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

   vector<int> linear_sieve(int n) {
   	vector<bool> is_prime(n + 1, true);
   	vector<int> primes;
   	is_prime[0] = is_prime[1] = 0; //0和1两个数特殊处理
   	for (int i = 2; i <= n; ++i) {
   		if (is_prime[i]) {
   			primes.push_back(i);
   		}
   		________________________________ { // 在此处填入代码
   		is_prime[i * primes[j]] = 0;
   		if (i % primes[j] == 0)
   			break;
   		}
   	}
   	return primes;
   }
   
   {{ select(5) }}
   
   

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

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

   高。

   {{ select(6) }}

• 正确
• 错误