题目描述
小 A 有一个质数口袋,里面可以装各个质数。他从 2 2 2 开始,依次判断各个自然数是不是质数,如果是质数就会把这个数字装入口袋。
口袋的负载量就是口袋里的所有数字之和。
但是口袋的承重量有限,装的质数的和不能超过 L L L。给出 L L L,请问口袋里能装下几个质数?将这些质数从小往大输出,然后输出最多能装下的质数的个数,数字之间用换行隔开。
输入格式
一行一个正整数 L L L。
输出格式
将这些质数从小往大输出,然后输出最多能装下的质数个数。
输入输出样例
输入
100
输出
2
3
5
7
11
13
17
19
23
9
说明/提示
数据保证, 1 ≤ L ≤ 10 5 1 \le L \le {10}^5 1≤L≤105。
方式
代码
class Solution:@staticmethoddef oi_input():"""从标准输入读取数据"""num = int(input())return num@staticmethoddef oi_test():"""提供测试数据"""return 100@staticmethoddef solution(num):from math import sqrtprime_nums, sum = [], 0for i in range(1, num + 1):if i in [2, 3, 5]:prime_nums.append(i)sum += iif i > 5:is_prime = Truefor i2 in range(2, int(sqrt(i)) + 1):if i % i2 == 0:is_prime = Falsebreakif is_prime:prime_nums.append(i)sum += iif sum > num:prime_nums.pop()breakfor i in prime_nums:print(i)print(len(prime_nums))oi_input = Solution.oi_input
oi_test = Solution.oi_test
solution = Solution.solutionif __name__ == '__main__':num = oi_test()# num = oi_input()solution(num)