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

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)

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(2条)

报告相同问题?

悬赏问题

  • ¥20 用泊松逆高斯分布拟合已知数据
  • ¥15 web课程,怎么做啊😭没好好听课 根本不知道怎么下手
  • ¥15 做一个关于单片机的比较难的代码,然后搞一个PPT进行解释
  • ¥15 python提取.csv文件中的链接会经常出现爬取失败
  • ¥15 数据结构中的数组地址问题
  • ¥15 maya的mel里,怎样先选择模型A,然后利用mel脚本自动选择有相同名字的模型B呢。
  • ¥15 Python题,根本不会啊
  • ¥15 会会信号与系统和python的来
  • ¥15 关于#python#的问题
  • ¥20 oracle RAC 怎么配置啊,配置