PTA:Python解答1007 素数对猜想

1007 素数对猜想 (20分)

让我们定义d​n​​ 为:d​n​​ = P​n+1​​ −Pn​​ ,其中pi​​ 是第i个素数。显然有d​1​​ =1,且对于n>1有d​n​​ 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。现给定任意正整数N(<10​5​​ ),请计算不超过N的满足猜想的素数对的个数。

输入格式:

输入在一行给出正整数N。

输出格式:

在一行中输出不超过N的满足猜想的素数对的个数。

输入样例:

20

输出样例:

4

解题思路:

素数对就是两个差为2的素数,如果按照正常思维直接求输入的数以内的素数,再确定哪些素数的差是2,很简单就能写出代码。但题目限制运行时间不能超过200ms,当输入的数较大时,用常规方法会超时。所以我们在这就用到素数筛选法,具体做法是:先把N个自然数按次序排列起来。1不是质数,也不是合数,要划去。第二个数2是质数留下来,而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3,把3留下,再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是5,把5留下,再把5后面所有能被5整除的数都划去。这样一直做下去,就会把不超过N的全部合数都筛掉,留下的就是不超过N的全部质数。

完整代码:

def prime(n, result):
    flag = [1] * (n + 2)
    p = 2
    while (p <= n):
        result.append(p)
        for i in range(2 * p, n + 1, p):
            flag[i] = 0
        while 1:
            p += 1
            if (flag[p] == 1):
                break

a = int(input())
result = []
prime(a, result)
num = 0
for i in range(len(result) - 1):
    if (result[i + 1] - result[i] == 2):
        num += 1
print(num)
点赞

发表评论

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