题目

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

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

输入格式:

输入在一行给出正整数N

输出格式:

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

输入样例:

20

输出样例:

4

解该题的思路有两个点,如何判断一个数是否是素数,判断相邻的素数之差是否为2
假设一个数为n,判断n是否为素数方法是用n去除从2到n的算术平方根之间的整数,如果能除尽,n为合数,如果都除不尽,n就是素数,python代码实现如下
import time
start = time.perf_counter()
def judgePrime(n):
for i in range(, int(n**0.5)+):
if(n % i == ):
return False
return True
num = int(input())
arr = [, ]
cnt =
if(num > ):
for i in range(, num+):
res = judgePrime(i)
if(res):
if(i - arr[len(arr)-] == ):
cnt +=
arr.append(i)
print(cnt,time.perf_counter()-start)

05-28 09:36