【python】pat-尊龙游戏旗舰厅官网

1. 题目描述

1007 素数对猜想 (20 分)

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

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

输入格式:

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

输出格式:

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

输入样例:

20

输出样例:

4

2. 题目分析

素数定义：在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

要求素数对，首先要求出<=n的全部素数，并把它放到一个list中。

所以自然而然想到要写出一个算法，判断一个数是否是素数

根据上面的流程，我们将其可以翻译成代码。

def isprime(n):if n == 1:return falseend = int(math.sqrt(n))for i in range(2, end1):if n % i == 0:return falsereturn true

但是这样写算法的运行效率非常慢。

这一题，限制的总耗时是200ms。

虽然上面的代码处理完全正确 , 但是最后一个测试点，直接运行超时，自然拿不到满分。

所以我们要设计运算速度更快的判断素数算法。

2,3,5,7,11,13,17,19,23

观察上面的数字，可以看出所有>6的素数，都可以采用 6k-1 或者 6k 1 的形式表示。（k>=1)

所以就设计出了算法2

def isprime(n):if n == 2 or n == 3:return trueif n % 2 == 0 or n % 3 == 0:return falsefor k in range(6,int(math.sqrt(n)) 2, 6):# range取值 [6,12,18,...]if n % (k-1) == 0 or n % (k1) == 0:return falsereturn true

3. ac代码

import mathdef isprime(n): # if n == 1: # return false # end = int(math.sqrt(n)) # for i in range(2, end 1): # if n % i == 0: # return false # return trueif n == 2 or n == 3:return trueif n % 2 == 0 or n % 3 == 0:return falsefor k in range(6,int(math.sqrt(n)) 2, 6):if n % (k-1) == 0 or n % (k1) == 0:return falsereturn truen = int(input()) l = [i for i in range(2, n1) if isprime(i)]count = 0for index, element in enumerate(l):if index < len(l)-1:if l[index1]-l[index] == 2:count = 1print(count) 与50位技术专家面对面20年技术见证，附赠技术全景图

总结

以上是尊龙游戏旗舰厅官网为你收集整理的【python】pat-1007-素数对猜想的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得尊龙游戏旗舰厅官网网站内容还不错，欢迎将尊龙游戏旗舰厅官网推荐给好友。