务虚心斋
2021-03-31 16:42
采纳率: 100%
浏览 74

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

 

 

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)
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

3条回答 默认 最新

  • 已采纳
    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)

    1 打赏 评论
  • 取平方根也是很耗时间的,不要重复的取平方根,所以取平方根要放在j循环外面。

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

    if j*j>i:

    打赏 评论
  • 有问必答小助手 2021-04-01 09:25

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

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

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

    打赏 评论

相关推荐 更多相似问题