题目
让我们定义dn为:dn=pn+1−pn,其中pi是第i个素数。显然有d1=1,且对于n>1有dn是偶数。“素数对猜想”认为“存在无穷多对相邻且差为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)