素数对猜想（20 分）

青旅半醒 2022-05-12 14:40 143阅读 0赞

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

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

## 输入格式: ##

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

## 输出格式: ##

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

## 输入样例: ##

20

## 输出样例: ##

4

普通求素数的算法会超时，要提高算法效率。

#include <bits/stdc++.h>
    using namespace std;
    int a[100001],p[100001];
    bool x[100001];
    int main()
    {
        
        int n,t=2,cnt=0;
        cin>>n;
        a[1]=2;
        for(int i=2; i<=n; i++){
        
            if(i%2)x[i]=true;
            else x[i]=false;
        }
        for(int i=3; i<=sqrt(n); i++){
        
            if(x[i]){
        
                for(int j=i+i; j<n; j=j+i){
        
                    x[j]=false;
                }
            }
        }
        for(int i=2; i<=n; i++){
        
            if(x[i]){
        
                a[t++]=i;
            }
        }
        for(int i=1; i<t; i++){
        
            p[i]=a[i+1]-a[i];
        }
        for(int i=1; i<t; i++){
        
            if(p[i]==2)cnt++;
        }
        cout<<cnt<<endl;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，143人围观）

还没有评论，来说两句吧...

相关阅读

相关 PAT乙级：1007 素数对猜想 (20 分)（Java）

PAT乙级：1007 素数对猜想 (20 分)（Java） > 作者 CHEN, Yue > 单位浙江大学 > 代码长度限制 16 KB > 时间限制 20

我会带着你远行/ 2022年10月14日 14:56/ 0 赞/ 193 阅读

相关 1007. 素数对猜想 (20)

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

Bertha 。/ 2022年08月23日 05:46/ 0 赞/ 162 阅读

相关 1007. 素数对猜想 (20)

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

曾经终败给现在/ 2022年08月23日 00:51/ 0 赞/ 199 阅读

相关 1007. 素数对猜想 (20)

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

Love The Way You Lie/ 2022年06月15日 10:13/ 0 赞/ 172 阅读

相关 1007. 素数对猜想 (20)

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

野性酷女/ 2022年05月31日 13:57/ 0 赞/ 212 阅读

相关 1007. 素数对猜想 (20)

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

向右看齐/ 2022年05月27日 01:41/ 0 赞/ 185 阅读

相关自测-2 素数对猜想（20 分）

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

清疚/ 2022年05月21日 07:43/ 0 赞/ 118 阅读

相关素数对猜想（20 分）

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

青旅半醒/ 2022年05月12日 14:40/ 0 赞/ 143 阅读

相关 1007 素数对猜想 (20 分)

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

阳光穿透心脏的1/2处/ 2021年12月19日 00:51/ 0 赞/ 243 阅读

相关 PAT 1007 素数对猜想 (20 分)（Java）

题目描述： ![在这里插入图片描述][20190822202034429.png] 输入格式: 输入在一行给出正整数N。输出格式: 在一行中输出

我不是女神ヾ/ 2021年09月23日 05:50/ 0 赞/ 276 阅读