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

问题描述：

1007 素数对猜想 (20 分)

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

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

输入格式:

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

输出格式:

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

输入样例:

输出样例:

题目网址：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)

答

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)

答

取平方根也是很耗时间的，不要重复的取平方根，所以取平方根要放在j循环外面。

其实可以反过来用j的平方和i比较，时间会少很多。

if j*j>i:

答

您好，我是有问必答小助手，你的问题已经有小伙伴为您解答了问题，您看下是否解决了您的问题，可以追评进行沟通哦~

如果有您比较满意的答案 / 帮您提供解决思路的答案，可以点击【采纳】按钮，给回答的小伙伴一些鼓励哦～～

ps:问答VIP仅需29元，即可享受5次/月有问必答服务，了解详情>>> https://vip.csdn.net/askvip?utm_source=1146287632

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

相关推荐