1007 素数对猜想 (20分)
让我们定义dn 为:dn = Pn+1 −Pn ,其中pi 是第i个素数。显然有d1 =1,且对于n>1有dn 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。现给定任意正整数N(<105 ),请计算不超过N的满足猜想的素数对的个数。
输入格式:
输入在一行给出正整数N。
输出格式:
在一行中输出不超过N的满足猜想的素数对的个数。
输入样例:
20
输出样例:
4
解题思路:
素数对就是两个差为2的素数,如果按照正常思维直接求输入的数以内的素数,再确定哪些素数的差是2,很简单就能写出代码。但题目限制运行时间不能超过200ms,当输入的数较大时,用常规方法会超时。所以我们在这就用到素数筛选法,具体做法是:先把N个自然数按次序排列起来。1不是质数,也不是合数,要划去。第二个数2是质数留下来,而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3,把3留下,再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是5,把5留下,再把5后面所有能被5整除的数都划去。这样一直做下去,就会把不超过N的全部合数都筛掉,留下的就是不超过N的全部质数。
完整代码:
def prime(n, result): flag = [1] * (n + 2) p = 2 while (p <= n): result.append(p) for i in range(2 * p, n + 1, p): flag[i] = 0 while 1: p += 1 if (flag[p] == 1): break a = int(input()) result = [] prime(a, result) num = 0 for i in range(len(result) - 1): if (result[i + 1] - result[i] == 2): num += 1 print(num)