首页 › 题库 › GESP编程能力等级认证 › 1.1 素数与合数

GESP-C++五级 题库

共 35 道题 ,第 1 / 2 页 · 按题型筛选,点「查看答案」核对解析
章节 1.1 素数与合数 清除
1 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

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

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; 
}


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

B
for(int j = sqrt(n); j <= n && i * primes[j] <= n; j++)

C
for (int j = 1; j <= sqrt(n); j++)

D
for(int j = 1; j < n && i * primes[j] <= n; j++)

答案与解析
正确答案:A
线性筛法通过标记合数的方式筛选素数,确保每个合数仅被其最小质因子筛除一次。外层循环遍历从2到n的整数i,若i未被标记,则将其加入素数表。内层循环需枚举已记录的素数j,用i与j的乘积标记合数,且当j能整除i时应终止以保证线性时间复杂度。内层循环的上限为当前已知素数个数,循环变量j作为素数列表的索引使用。
题目详情
2 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

下列C++代码判断一个正整数是否是质数,说法正确的是?( )

bool is_prime(int n) {
    if (n <= 1)
        return false;
    if (n == 2 || n == 3 || n == 5)
        return true;
    if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0)
        return false;
    int i = 7;
    int step = 4;
    int finish_number = sqrt(n) + 1;
    while (i <= finish_number) {
        if (n % i == 0)
            return false;
        i += step;
        step = 6 - step;
    }
    return true;
}
A
代码存在错误,比如5是质数,但因为 5 % 5 余数是0返回了 false
B
finish_number 的值应该是 n / 2 ,当前写法将导致错误
C
当前 while 循环正确的前提是:所有大于3的质数都符合 6k±1 形式
D
while 循环修改如下,其执行效果和执行时间相同。
for (int i = 2; i < finish_number; i++) {
    if (n % i == 0)
        return false;
}
return true;
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
3 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

下面的代码用于判断整数 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;
}
A
埃氏筛算法相对于上面的代码效率更高
B
线性筛算法相对于上面的代码效率更高
C
上面的代码有很多重复计算,因为不是判断单个数是否为质数,故而导致筛选出连续数中质数的效率不高
D
相对而言,埃氏筛算法比上面代码以及线性筛算法效率都高
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
4 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

下述代码实现素数表的线性筛法,筛选出所有小于等于 n 的素数,横线上应填的最佳代码是?( )

vector<int> sieve_linear(int n) {
    vector<bool> is_prime(n +1, true);
    vector<int> primes;
    if (n < 2) return primes;
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i <= n/2; 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;
        }
    }
    for (int i = n/2 +1; i <= n; i++) {
        if (is_prime[i])
            primes.push_back(i);
    }
    return primes;
}
A
j < primes.size()
B
i * primes[j] <= n
C
j < primes.size() && i * primes[j] <= n
D
j <= n
答案与解析
正确答案:C

线性筛法的核心思想是 每个合数只被其最小质因数筛除一次,从而保证 O(n) 的时间复杂度。

内层循环的目的是 筛除 i×primes[j],因此需要满足:

j 不超过 primes 数组的大小(避免越界访问)。

i×primes[j]≤n(筛除的合数不能超过 n)。

本题答案为选项C。

题目详情
5 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

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

#include <vector>
vector<int> get_prime_factors(int n) {
	vector<int> factors;
	if (n <= 1) {
		cout << "输入的数必须是大于1的正整数" << endl;
		return;
	}
	while (n % 2 == 0) {
		factors.push_back(2);
		n /= 2;
	}
	
	________________________________ { // 在此处填入代码
		while (n % i == 0) {
			factors.push_back(i);
			n /= i;
		}
	}
	
	if (n > 2) {
		factors.push_back(n);
	}
	
	return factors;
}
A
for (int i = 3; i <= n; i ++)
B
for (int i = 3; i * i <= n; i ++)
C
for (int i = 3; i <= n; i += 2)
D
for (int i = 3; i * i <= n; i += 2)
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
6 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

下述代码实现素数表的埃拉托色尼(埃氏)筛法,筛选出所有小于等于 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;
}

下面说法,正确的是( )。

A
代码的时间复杂度是 O(nn)。
B
在标记非素数时,代码从 i2开始,可以减少重复标记。
C
代码会输出所有小于等于 n 的奇数。
D
调用函数 sieve_Eratosthenes(10) ,函数返回值的数组中包含的元素有: 2, 3, 5, 7, 9 。
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
7 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.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);
			
		for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) {
			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;
}
A
线性筛的时间复杂度是 O(n)。
B
每个合数会被其所有的质因子标记一次。
C
线性筛和埃拉托色尼筛的实现思路完全相同。
D
以上都不对
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
8 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

下述代码实现素数表的埃拉托斯特尼筛法,筛选出所有小于等于 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);
			________________________________ { // 在此处填入代码
				is_prime[j] = false;
			}
		}
	}
	
	for (int i = sqrt(n) + 1; i <= n; i++) {
		if (is_prime[i]) {
			primes.push_back(i);
		}
	}
	
	return primes;
}


A
for (int j = i; j <= n; j++)
B
for (int j = i * i; j <= n; j++)
C
for (int j = i * i; j <= n; j += i)
D
for (int j = i; j <= n; j += i)
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
9 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.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;
}


A
for (int j = 0; j < primes.size() && i * primes[j] <= n; j++)
B
for (int j = 1; j < primes.size() && i * j <= n; j++)
C
for (int j = 2; j < primes.size() && i * primes[j] <= n; j++)
D
以上都不对
答案与解析
正确答案:A

这个地方是要枚举质数表,然后把质数的i倍数都筛掉,所以应该是选A。

题目详情
10 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

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

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;
}
A
or (int j = 0; j < primes.size() && i * primes[j] <= n; j++)
B
for (int j = 0; j <= sqrt(n) && i * primes[j] <= n; j++)
C
for (int j = 0; j <= n; j++)
D
for (int j = 1; j <= sqrt(n); j++)
答案与解析
正确答案:A

使用for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) 这个循环来遍历当前已知的素数列表primes,确保了我们使用当前素数i 来乘以已知素数primes[j],并且正确地筛选掉不超过n 的合数。

题目详情
11 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

下面的代码片段用于判断一个正整数是否为素数。请对以下代码进行修改,使其能正确实现相应功能。(   )

bool isPrime(int num) {
	if (num < 2) {
		return false;
	}
	for (int i = 2; i * i < num; ++i) {
		if (num % i == 0) {
			return false;
		}
	}
	return true;
}
A
num < 2 应该改为 num <= 2
B
循环条件 i * i < num 应该改为 i * i <= num
C
循环条件应该是 i <= num
D
循环体中应该是 if (num % i != 0)
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
12 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

在埃拉托斯特尼筛法中,要筛选出不大于 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;
}
A
for (int i = 2; i <= n; ++i)
B
for (int i = 1; i < n; ++i)
C
for (int i = 2; i <= sqrt(n); ++i)
D
for (int i = 1; i <= sqrt(n); ++i)
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
13 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

素数的线性筛法时间复杂度为(   )。

A
O(n)
B
O(nloglogn)
C
O(nlogn)
D
O(n2)
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
14 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

下面C++代码中的 isPrimeA() 和 isPrimeB() 都用于判断参数N是否素数,有关其时间复杂度的正确说法是(   )。

A

isPrimeA( ) 的最坏时间复杂度是, isPrimeB( ) 的最坏时间复杂度是, isPrimeA() 优于 isPrimeB()

B

isPrimeA() 的最坏时间复杂度是, isPrimeB( ) 的最坏时间复杂度是, isPrimeB() 绝大多数情况下优于 isPrimeA()

C

isPrimeA() 的最坏时间复杂度是, isPrimeB( ) 的最坏时间复杂度是, isPrimeA( ) 优于isPrimeB( )

D

isPrimeA() 的最坏时间复杂度是, isPrimeB( ) 的最坏时间复杂度是, isPrimeA() 优于isPrimeB( )

答案与解析
正确答案:B
这道题暂未补解析。
题目详情
15 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

小杨想编写一个判断任意输入的整数N是否为素数的程序,下面哪个方法不合适?(   )(2023年12月C++五级)

A

埃氏筛法

B

线性筛法

C

二分答案

D

枚举法

答案与解析
正确答案:C
这道题暂未补解析。
题目详情
16 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

下面代码中的 isPrimeA() 和 isPrimeB() 都用于判断参数 N 是否素数,有关其时间复杂度的正确说法是(     )。

A
isPrimeA() 的最坏时间复杂度是O(N), isPrimeB() 的最坏时间复杂度是O(logN), isPrimeB() 优于isPrimeA() 。
B
isPrimeA() 的最坏时间复杂度是O(N), isPrimeB() 的最坏时间复杂度是O(N1/2), isPrimeB() 优于isPrimeA() 。
C
isPrimeA() 的最坏时间复杂度是O(N1/2), isPrimeB() 的最坏时间复杂度是O(N), isPrimeA() 优于isPrimeB() 。
D
isPrimeA() 的最坏时间复杂度是O(logN), isPrimeB() 的最坏时间复杂度是O(N), isPrimeA() 优于isPrimeB()
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
17 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

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

A
对
B
错
答案与解析
正确答案:错
分析两种筛法的执行机制:线性筛法通过每个合数仅被其最小质因子标记一次,确保每个数被访问的次数为常数级;埃氏筛法对每个质数的倍数进行标记,存在重复标记同一合数的情况。比较两者操作步骤的数量增长趋势,观察内层循环的触发条件及执行频率,推导各自的时间复杂度表达式。注意算法实现中是否包含冗余操作,以及标记过程的范围和终止条件如何影响总体运算量。
题目详情
18 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

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

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
19 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

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

vector<int> linearSieve(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 j = 0; j < primes.size() && i * primes[j] <= n; ++j) {
            is_prime[i * primes[j]] = false;
            if (i % primes[j] == 0) {
                break;
            }
        }
    }
    return primes;
}
A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
20 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 1.1 素数与合数

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

A
对
B
错
答案与解析
正确答案:对

线筛的时间复杂度是 O(n),每个合数只被其最小质因数筛去一次。

而埃筛的时间复杂度是 O(nlog log n),相对来说会更高,是在筛选过程中存在重复操作。

本题答案为正确。

题目详情