欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

问题分析:

  1. 这个问题素数的算法,为提升计算速度防止超时,参考之前的素数筛选法
  2. 本题需要计算最后一位素数的大小,这个数学问题我是真的不会啊(╥﹏╥…)
    于是乎参考了一下贴吧大神的算法
    .
    用 px 表示 第x个素数,如果 x > 6
    则有
    x ln x + x ln ln x - x < px
    并且
    px < x ln x + x ln ln x
    .
    emmmm…虽然不知道是怎么来的,但是是可以用的
  3. 需要注意输出时的换行问题

代码:

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="")
相关标签: PAT 1013