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

GESP-Python五级 题库

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

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

def linear_sieve(n) :
    if n < 2 :
        return []
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    primes = []
    for i in range(2 , n + 1) :
        if is_prime[i] :
            primes.append(i)
        for j in range(len(primes)) :
            p = primes[j]
            if i * p > n:
                break
            # 填空位置
            if i % p == 0 :
                break
    return primes
A
is_prime [i * p] = False
B
is_prime [i] = False
C
is_prime [i * p] = True
D
is_prime [i + p] = False
答案与解析
正确答案:A
线性筛核心:将i*p标记为合数,填入`is_prime[i*p] = False`。
题目详情
2 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 1.1 素数与合数

下列Python代码用于判断一个正整数是否是质数(素数),相关说法中正确的是( )。

A

代码存在错误,比如5是质数,但因为 5 % 5 余数是0返回了False

B

finish_number 的值应该是 N // 2 ,当前写法将导致错误

C

当前while循环正确的前提是:所有大于3的质数都符合 6k±1 形式

D

while循环修改如下,其执行效果与执行时间相同

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

下面的代码用于列出求1到N之间的所有质数,错误的说法是( )。

A

埃氏筛算法相对于上面的代码效率更高

B

线性筛算法相对于上面的代码效率更高

C

上面的代码,有很多重复计算,因为不是判断单个数是否为质数,故而导致筛选出连续数中质数的效率不高

D

相对而言,埃氏筛算法比上面代码以及线性筛算法效率都高

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

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

def sieve_linear(n):
	is_prime = [True] * (n + 1)
	primes = []

	if n < 2:
		return primes #

	is_prime[0] = is_prime[1] = False

	for i in range(2, n // 2 + 1):
		if is_prime[i]:
		primes.append(i)


	j = 0
	_____________________________________
		is_prime[i * primes[j]] = False
		if i % primes[j] == 0:
			break
		j += 1


	for i in range(n // 2 + 1, n + 1):
		if is_prime[i]:
		primes.append(i)

	return primes
A
while j < len(primes) and j * primes[j] <= n:
B
while j < len(primes) and i * primes[j] <= n:
C
while j < len(primes) and j * primes[i] <= n:
D
while i < len(primes) and i * primes[j] < n:
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
5 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 1.1 素数与合数

18到100之间的所有素数的和为多少( )

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

下列程序是素数筛的程序,横线处应该填上( )。

def sieve(n):
	if n < 2:
		return []
	prime = [True] * (n+1)
	prime[0] = prime[1] = False
	for i in range(2, int(math.sqrt(n)) + 1):
		if prime[i]:
			_______________________
				prime[j] = False
	return [p for p in range(2, n+1) if prime[p]]
for prime in sieve_of_eratosthenes(100):
	print(prime)


A
for j in range(i, n+1, i):
B
for j in range(ii, 1, n):
C
for j in range(ii, n+1, i):
D
for j in range(i, n, i):
答案与解析
正确答案:C

第7行判断如果当前i是质数,则i的倍数都不是质数,所以这个地方是要枚举i的所有的倍数,注意右边界。

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

下面是埃氏素数筛的Python实现,横线上应填入的代码是( )。

def listPrime(N):
	primeList = list(range(N+1))
	primeList[0] = primeList[1] = False
	for i in range(2,int(N ** 0.5) + 1):
		if primeList[i] != False:
			for j in range(_____________):
				primeList[j] = False
	return [x for x in primeList if x != False]
A
i + i, N + 1, 2
B
i * i, N + 1, i
C
i * i, N, i * i
D
i, N + 1, i
答案与解析
正确答案:B

埃氏筛法(埃拉托斯特尼筛法)是一种用于查找一定范围内所有素数的有效算法

我们需要填入的三个空白分别是:

第一个空白:表示从i*i 开始标记非素数。

第二个空白:表示循环范围,即N 之内需要标记非素数。

第三个空白:表示步长,即每次增加i。

i * i, N + 1, i

第一个空白:i * i,从i*i 开始标记非素数。

第二个空白:N + 1,循环范围是正确的。

第三个空白:i,表示每次增加i,符合埃氏筛法的步长要求。

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

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

A

埃氏筛法

B

线性筛法

C

二分答案

D

枚举法

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

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

A

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

B

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

C

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

D

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

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

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

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

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

A
对
B
错
答案与解析
正确答案:对
埃氏筛存在重复标记合数,线性筛每个合数仅标记一次,效率更高。
题目详情
12 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 1.1 素数与合数

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

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

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

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

任何一个大于1的自然数都可以分解成若干个不同的质数的乘积,且分解方式是唯一的。

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

要得到不大于某个自然数 n (不等于0)的所有素数,只要在2至 n 中将不大于的素数的倍数全部划去即可

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

每个大于1的整数可以唯一地写成质数的乘积的形式

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

唯一分解定理概念:任意大于等于2的整数,都可以唯一分解位若干个质数的幂次方的乘积的形式。

题目详情
17 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 1.1 素数与合数

求解指定正整数范围内所有质数,采用线性筛算法比埃氏筛效率更高。( )

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

埃氏筛:算法思想,从小到大枚举每个素数,将其所有的倍数标记为非素数。效率,时间复杂度约为O(n log log n),其中n是给定范围内的最大整数。

线性筛法:算法思想,类似于埃氏筛,但是通过线性的方式来标记非素数,而不是简单地使用倍数关系。效率,时间复杂度为O(n),相对于埃氏筛有更好的性能。

题目详情
18 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 1.1 素数与合数

找出自然数N以内的所有质数常用埃氏筛法,其时间复杂度为 0(N)。

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

相等序列
时间限制:3.0 s
内存限制:512.0 MB
题目描述

小 A 有一个包含 N 个正整数的序列A = {A₁ , A₂ , · · ,A_N}。小 A 每次可以花费 1 个金币执行以下任意一种操作:

1. 选择序列中一个正整数 A_i( 1 ≤ i ≤ N),将 A_i 变为 A_i × P,P 为任意质数;
2. 选择序列中一个正整数 A_i( 1 ≤ i ≤ N),将 A_i 变为 A_i ÷ P,P 为任意质数,要求 A_i 能整除 P。
小 A 想请你帮他计算出令序列中所有整数都相同,最少需要花费多少金币。
输入格式
第一行一个正整数 N,含义如题面所示。
第二行包含 N 个正整数 A₁ , A₂ , · · ,A_N,代表序列 A。
输出格式
输出一行,代表最少需要花费的金币数量。
样例
输入样例

5
10  6  35  105  42

输出样例

8

数据范围
对于60%的测试点,保证 1 ≤ N, A_i ≤ 100。
对于所有测试点,保证 1 ≤ N, A_i ≤ 10⁵。

答案与解析
参考答案
tokens = []
def get_val() :
    while not tokens:
        tokens.extend(input().split())
    return int(tokens.pop(0))

# 一共有多少数
n = get_val()
# key:质数
# value:一个列表 ,num[p][exp]表示有多少数质因数分解后可以包含p^exp
# 因为一个数最大就到10^5 ,相当于是10w ,所以列表最多包含20个数肯定够用 ,即2^20
num = {}

for _ in range(n) :
    # 统计一下各个输入数字有多少质因数
    x = get_val()
    d = 2
    # 质因数必定小于根号x
    tmp = x
    while d * d <= tmp:
        # 如果找到了一个数是x的因数
        if tmp % d == 0 :
            cnt = 0
            # 那就一直除以这个数 ,并且更新x的质因数数目
            # 这样一来剩下能够整除x的必定是质数
            while tmp % d == 0 :
                tmp //= d
                cnt += 1
            if d not in num:
                num[d] = [0] * 20
            # 数字x包含d^cnt ,更新状态
            num[d][cnt] += 1
        d += 1
    # 如果x是质数
    if tmp > 1 :
        if tmp not in num:
            num[tmp] = [0] * 20
        num[tmp][1] += 1

ans = 0
for p in num:
    counts = num[p]
    # 计算有多少数字不包含这个质因数
    counts[0] = n - sum(counts)
    # 寻找中位数指数
    # 也就是寻找一个指数e,使得一半的数字包含超过e次方的p,另一半不包含
    pos = 0
    median_exponent = 0
    for j in range(20) :
        pos += counts[j]
        if pos * 2 >= n:
            median_exponent = j
            break
    # 计算代价
    for j in range(20) :
        if counts[j] :
            ans += counts[j] * abs(j - median_exponent)
print(ans)
题目详情
20 简答题 偏难 GESP编程能力等级认证 ·GESP-Python五级 · 1.1 素数与合数

原根判断

题目描述

小 A 知道,对于质数p 而言,p 的原根g 是满足以下条件的正整数:

·1<g<p

·gp-1 mod p=1

·对于任意1≤i<p-1 均有 gi mod p≠1。

其中a mod p 表示a 除以 p的余数。

小 A 现在有一个整数a ,请你帮他判断 a是不是p 的原根。

输入格式

第一行,一个正整数 T,表示测试数据组数。

每组测试数据包含一行,两个正整数a ,p 。

输出格式

对于每组测试数据,输出一行,如果 a是 p的原根则输出 Yes ,否则输出 No 。


输入样例

3
3 998244353
5 998244353
7 998244353

输出样例

Yes
Yes
No

数据范围

对于 40% 的测试点,保证3≤p≤103 。

对于所有测试点,保证1≤T≤20 ,3≤p≤109,1<a<p ,p为质数。

答案与解析
参考答案
def fpw(b, e, p):
	if e == 0:
		return 1
	r = fpw(b, e >> 1, p)
	return r * r * (b if e & 1 else 1) % p

def solve():
	a, p = map(int, input().split())
	phi, v = p - 1, p - 1
	for i in range(2, int(phi ** 0.5) + 2):
		if v % i == 0:
			while v % i == 0:
				v //= i
			if fpw(a, phi // i, p) == 1:
				print("No")
				return
	if v > 1:
		if fpw(a, phi // v, p) == 1:
			print("No")
			return
	print("Yes")

[solve() for _ in range(int(input()))]
题目详情