【python_PAT_乙类】1007_素数对猜想，Python运行超时解决方案

CloudXli

2020-06-11

题目：

让我们定义d?n??为：d?n??=p?n+1??−p?n??，其中p?i??是第i个素数。显然有d?1??=1，且对于n>1有d?n??是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。
现给定任意正整数N(<)，请计算不超过N的满足猜想的素数对的个数。
输入格式:
输入在一行给出正整数N。
输出格式:
在一行中输出不超过N的满足猜想的素数对的个数。

输入样例:
20 
输出样例:
4

　思路：

1、常规判断素数，i+2 的值与 i进行比较（以3开始，且偶数排除），超时

2、开根号判断素数，以素数生成一个列表（以3开始，且偶数排除），列表里进行比较，超时

3、开根号判断素数，根据特性，判断当前是不是素数，不是素数，判断列表的最后一位与当前是不是差2，如果差2则移除列表最后一项值，保证列表中的值是既是素数且有素数对，在最终生成的列表项的最后一项需要做额外处理，需要判断最后1项是否有素数对。

代码如下：

# 素数对猜想
import math


def is_prime_num(test_num):
    for i in range(3, int(math.sqrt(test_num)+1), 2):
        if test_num % i == 0:
            return False
    return True


num = int(input())
count_num = 0
i = 3
list_num = []
while 2 < i <= num-2:
    if is_prime_num(i):
        list_num.append(i)
    elif i - list_num[-1] == 2:
        del list_num[-1]
    i = i + 2
if (not is_prime_num(num)) and num - list_num[-1] == 2:
    del list_num[-1]
print(len(list_num))

运行结果：

【python_PAT_乙类】1007_素数对猜想，Python运行超时解决方案