1007 素数对猜想 (20 分)

1007 素数对猜想 (20 分),第1张

1007 素数对猜想 (20 分)

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

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

输入格式:

输入在一行给出正整数N。

输出格式:

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

输入样例:
20

结尾无空行

输出样例:
4

结尾无空行

N = 100010

primes = [0] * N
cnt = 0
st = [0] * N

# 质数的倍数肯定不是质数,每一次都拿质数的倍数去筛掉合数, 存在一个合数被其本身多个质因子重复筛
def get_Primes_1():
    global cnt
    for i in range(2, N):
        if not st[i]:
            primes[cnt] = i
            cnt += 1
            for j in range(i + i, N, i):
                st[j] = True

#每一次都拿最小的质因子去筛掉合数,保证了每一个合数都只会被筛一次
def get_Primes_2():
    global cnt
    for i in range(2, N):
        if not st[i]:
            primes[cnt] = i
            cnt += 1
        
        j = 0
        while i * primes[j] < N:
            # 最小质因子primes[j]去筛掉合数
            st[i * primes[j]] = True
            # 不是最小质因子,防止被多次筛,直接退出
            if i % primes[j] == 0:
                break
            j += 1

get_Primes_2()

n = int(input())

res = 0
for i in range(1, cnt):
    if primes[i] > n:
        break
    if primes[i] - primes[i - 1] == 2:
        res += 1
print(res)

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5691052.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存