PAT 1013 数素数 pyton (无超时)
程序员文章站
2022-04-24 13:33:32
...
1013 数素数 (20)(20 分)
令P~i~表示第i个素数。现任给两个正整数M <= N <= 10^4^,请输出P~M~到P~N~的所有素数。
输入格式:
输入在一行中给出M和N,其间以空格分隔。
输出格式:
输出从P~M~到P~N~的所有素数,每10个数字占1行,其间以空格分隔,但行末不得有多余空格。
输入样例:
5 27
输出样例:
11 13 17 19 23 29 31 37 41 43
47 53 59 61 67 71 73 79 83 89
97 101 103
作者: CHEN, Yue
单位: PAT联盟
时间限制: 200ms
内存限制: 64MB
代码长度限制: 16KB
问题分析:
- 这个问题素数的算法,为提升计算速度防止超时,参考之前的素数筛选法
- 本题需要计算最后一位素数的大小,这个数学问题我是真的不会啊(╥﹏╥…)
于是乎参考了一下贴吧大神的算法
.
用 px 表示 第x个素数,如果 x > 6
则有
x ln x + x ln ln x - x < px
并且
px < x ln x + x ln ln x
.
emmmm…虽然不知道是怎么来的,但是是可以用的 - 需要注意输出时的换行问题
代码:
import math
num = input().split()
prime = []
# 判断最后一个素数的大小
x = float(num[1])
if x > 6:
n = x * math.log(x) + x * math.log(math.log(x))
n = int(n)
else:
n = 15
flag = [1] * (n + 2)
p = 2
while p <= n:
prime.append(p)
for i in range(2 * p, n + 1, p):
flag[i] = 0
while 1:
p += 1
if flag[p] == 1:
break
# 对需要的部分进行切片
rst = prime[int(num[0]) - 1:int(num[1])]
if len(rst) == 1:
print(rst[0])
else:
for i in range(len(rst) - 1):
if (i+1) % 10 == 0:
print(rst[i])
else:
print(rst[i], end=" ")
else:
if len(rst) % 10 == 0:
print(rst[-1])
else:
print(rst[-1], end="")
下一篇: CAD怎么建模三维零件模型?