自测-2 素数对猜想 (PTA)

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

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

输入格式:

输入在一行给出正整数N

输出格式:

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

输入样例:

20

输出样例:

4

编译器:Python(python3)

 def eratosthenes(n):
    IsPrime = [True] * (n + 1)
    for i in range(2, int(n ** 0.5) + 1):
        if IsPrime[i]:
            for j in range(i * i, n + 1, i):
                IsPrime[j] = False
    return [x for x in range(2, n + 1) if IsPrime[x]]
n=int(input())
result = eratosthenes(n)
#print(result)
count = 0;
for i in range(len(result) - 1):
    if result[i+1]-result[i]== 2:
        count +=1;
print(count) 

Python的问题还是消耗的资源多,用普通的算法最大N总是超时,这里使用了Sieve of Eratosthenes

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
https://zh.wikipedia.org/wiki/%E5%9F%83%E6%8B%89%E6%89%98%E6%96%AF%E7%89%B9%E5%B0%BC%E7%AD%9B%E6%B3%95
中文的wiki上有现成的代码

发表评论

您的电子邮箱地址不会被公开。