PTA：Python解答1007 素数对猜想

让我们定义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)