pta拼题：1007 素数对猜想 (20 分)，总是超时

Question

 

 

1007 素数对猜想 (20 分)

让我们定义d​n​​为：d​n​​=p​n+1​​−p​n​​，其中p​i​​是第i个素数。显然有d​1​​=1，且对于n>1有d​n​​是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。

现给定任意正整数N(<10​5​​)，请计算不超过N的满足猜想的素数对的个数。

输入格式:

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

输出格式:

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

输入样例:

20

输出样例:

4

题目网址：https://pintia.cn/problem-sets/994805260223102976/problems/994805317546655744

import math

def Prime_list(n):
    prime_list =[2]
    for i in range(3,n+1,2):
        for j in prime_list:
            if i%j == 0 :
                break
        else:
            prime_list.append(i)
    return prime_list
    
num=int(input())

prime_list = Prime_list(num)
count = 0
l = len(prime_list)
for n in range(l-1):
    if prime_list[n+1] - prime_list[n] == 2:
        count += 1

print(count)

Answer 1

import math

def Prime_list(n):
    prime_list = [2]
    for i in range(3,n+1,2):
        k = math.ceil(math.sqrt(i))
        for j in prime_list:
            if i%j == 0:
                break
            if j>k:
                prime_list.append(i)
                break
        else:
            prime_list.append(i)
    return prime_list

num=int(input())
prime_list = Prime_list(num)
count = 0
l = len(prime_list)
for n in range(l-1):
    if prime_list[n+1] - prime_list[n] == 2:
        count += 1
print(count)