让我们定义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
求解出1到N范围内的素数，然后遍历此序列统计相邻素数差为2的素数对个数，重点在于判断素数的方法。
1. 素数就是一个只能被1和自己整除的正整数 - 枚举法
只有1和它本身两个因数的自然数是素数，否则就叫合数。
def isPrime( N ): """ judge whether N is a prime number param: N (int) retype: bool """ if N <= 1: return False else: flag = True
# from 2 to N-1 for i in range(2, N): if (N % i) == 0: flag = False break return flag
2.数N如果不能被小于它的平方根√N整除，就是素数 - 开方判断素数法
假设N是一个合数，N = a*b,a为N的约数。a、b中肯定存在一个数>=根号N，另一个数<=根号N。
只要<=根号N的数不能整除N,那么N就不存在除1外的因数。则N为素数。
import math def isPrimeSqrt( N ): if N <= 1: return False else: flag = True num = int( math.sqrt(N) ) for i in range(2, num+1): if (N % i) == 0: flag = False break return flag
3. - 埃氏素数筛法
python版本
import math def isPrimeSqrt( N ): if N <= 1: return False else: flag = True num = int( math.sqrt(N) ) for i in range(2, num+1): if (N % i) == 0: flag = False break return flag def isPrime( N ): """ judge whether N is a prime number param: N (int) retype: bool """ if N <= 1: return False else: flag = True for i in range(2, N): if (N % i) == 0: flag = False break return flag def generatePrime( N ): prime = [ i for i in range(1,N+1) if isPrime(i) ] return prime N = int( input() ) cntPrimePair = 0 differ = 0 #for i in N: primes = generatePrime( N ) length = len(primes) for i in range(length): if i < (length - 1): differ = primes[i+1] - primes[i] if differ == 2: cntPrimePair += 1 print(cntPrimePair)
原文：https://www.cnblogs.com/justLittleStar/p/10675816.html