题解 CF17A 【Noldbach problem】

发表于 | 更新于 | 评论数： | 阅读次数：
本文字数： 1.7k | 阅读时长 ≈ 2 分钟

题目要求的是一个素数与它相邻的素数之和$+1$为素数（注意这个素数要$\le n$）

思路：

  • 预处理$2$~$n$的素数

  • 暴力枚举

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
int p[1010],len,n,sum,k;
bool prime(int num)//素数判断
{
    if(num<2) return 0;
    if(num==2 or num==3) return 1;
    if(num%6!=5 and num%6!=1) return 0;
    for(int i=5;i*i<=num;i+=6)
    {
        if(num%i==0 or num%(i+2)==0)
          return 0;
    }
    return 1;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>k;
    for(int i=2;i<=n;i++)//预处理
    {
        if(prime(i))
          p[++len]=i;
    }
    for(int i=2;i<=len;i++)//枚举
    {
        if(prime(p[i-1]+p[i]+1) and p[i-1]+p[i]+1<=n)
            sum++; 
    }
    cout<<(sum>=k?"YES":"NO");//相当于if(sum>=k) cout<<"YES";else cout<<"NO";
    return 0;
}

用时：$1024ms$

我们可以在原来的程序做一些小小的优化

对枚举部分，我们加入一个边界条件

$p[i-1]+p[i] \le n$（$p[i]$为素数）

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
int p[1010],len,n,sum,k;
bool prime(int num)
{
    if(num<2) return 0;
    if(num==2 or num==3) return 1;
    if(num%6!=5 and num%6!=1) return 0;
    for(int i=5;i*i<=num;i+=6)
    {
        if(num%i==0 or num%(i+2)==0)
          return 0;
    }
    return 1;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>k;
    for(int i=2;i<=n;i++)
    {
        if(prime(i))
          p[++len]=i;
    }
    for(int i=2;i<=len and p[i-1]+p[i]+1<=n;i++)//边界条件
    {
        if(prime(p[i-1]+p[i]+1))
            sum++; 
    }
    cout<<(sum>=k?"YES":"NO");
    return 0;
}

用时：$994ms$ （$emmm$才快了$30ms$）