PTA:Python解答1013 数素数

1013 数素数 (20分)

令Pi表示第i个素数。现任给两个正整数M≤N≤10^4,请输出PM到PN的所有素数。

输入格式:

输入在一行中给出 M 和 N,其间以空格分隔。

输出格式:

输出从PM到PN的所有素数,每 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

解题思路:

在算素数时,为了提升速度,我们还是使用1007素数对猜想的素数筛选法。这道题的不同之处在于,该题并未给出查找素数的具体范围,而是给出希望得到的素数个数。所以为了满足所有的测试用例,我们要给出一个合适的计算范围(n)。我们可以设定一个很大的数,直接来限制计算范围,但是这样计算时间就会变得很长,虽然完成该题基本上可以在限定时间内通过,但是如果题目要求的不是10^4,而是10^5、10^6这种更大数,就花的时间太久了。但有个规律是:令Pi表示第i个素数,当i>6时,Pi<x*lnx+x*ln(lnx),当i≤6,Pi一定小于14。这样,不管最大取值是多少,计算范围永远比他大不了多少,整个程序的速度也能提升。

完整代码:

import math
num = input().split()
ls = []
x = int(num[1])
if x > 6:     
    n = x * math.log(x) + x * math.log(math.log(x))
    n = int(n)
else:
    n = 14
flag = [1] * (n + 2)
p = 2
while p <= n:
    ls.append(p)
    for i in range(2 * p, n + 1, p):
        flag[i] = 0
    while 1:
        p += 1
        if flag[p] == 1:
            break

rst = ls[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="")

我的提交结果,可以看到运行时间很短

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注