P5723 [Deep Foundation 4.Example 13] Python3 对质数口袋的实现

刚学Python的菜狗

a=int(input())
b=list()
n=0
sum=0
if a!=1:
    for i in range(2, a + 1):
        b.append(i)
    for i in range(0, a):
        c = 2
        while c < b[i]:
            s = b[i] % c
            if s == 0:
                break
            else:
                c += 1
        if b[i] == c:
            sum += b[i]
            if sum <= a:
                print(b[i])
                n += 1
            else:
                break
        i += 1
        if i >= len(b):
            break
    print(n)
else:
    print(0)

先把2到输入的数字用循环存入列表，然后挨个判断是否为质数，时间复杂度高.

优化后

def is_prime(n):
    # 判断一个数是否为质数
    if n < 2:  # 小于 2 的数不是质数
        return False
    for i in range(2, int(n**0.5) + 1):  # 遍历 2 到 sqrt(n) 的范围
        if n % i == 0:  # 如果存在能整除 n 的数，n 不是质数
            return False
    return True  # 否则，n 是质数

L = int(input())  # 输入 L 的值

pocket = []  # 存放质数的口袋
total_sum = 0  # 当前口袋内质数的和

for num in range(2, L+1):  # 从 2 开始到 L 进行遍历
    if is_prime(num):  # 判断 num 是否为质数
        if total_sum + num <= L:  # 如果当前质数总和加上 num 小于等于 L
            pocket.append(num)  # 将 num 添加到口袋中
            total_sum += num  # 更新质数总和
        else:
            break  # 如果超过 L，跳出循环

for prime in pocket:
    print(prime)  # 输出口袋中的质数

print(len(pocket))  # 输出口袋中质数的个数