问题 C: Goldbach's Conjecture

样例输出

1
2
2

题意：给出大于等于4的数p 然后找出俩个素数相加为p p1+p2 和 p2+p1 算一种


这个就是判断  <=n/2 的数 然后访问vis[i]&&vis[n-i] 都是素数  那么就是even number

#include<bits/stdc++.h>

using namespace std;
const int N=4e4;
int prime[N];
bool vis[N];
int cnt=0;
void isprime(int n)
{
    fill(vis,vis+N,false);
    cnt=0;
    for(int i=2; i<n; i++)
    {
        if(!vis[i])
        {
            prime[cnt++]=i;
        }
        for(int j=i+i; j<n; j+=i)
        {
            vis[j]=true;
        }
    }
}
int main()
{
    int n;
    isprime(N);
    while(scanf("%d",&n)==1,n){
        int sum=0;
        for(int i=2;i<=n/2;i++){
            if(!vis[i]&&!vis[n-i]) sum++;
        }
        printf("%d\n",sum);
    }
    return 0;
}

直接模拟下 也行 但是复杂度是n^2

#include<bits/stdc++.h>
  
using namespace std;
const int N=1e6+10;
int prime[N];
bool vis[N];
int cnt=0;
void isprime(int n)
{
    fill(vis,vis+N,false);
    cnt=0;
    for(int i=2; i<n; i++)
    {
        if(!vis[i])
        {
            prime[cnt++]=i;
        }
        for(int j=i+i; j<n; j+=i)
        {
            vis[j]=true;
        }
    }
}
int main()
{
    int n;
    while(scanf("%d",&n)==1,n){
        isprime(n);
        int sum=0;
        int flag=0;
        for(int i=0;i<cnt;i++){
            for(int j=i;j<cnt;j++){
                if(prime[i]+prime[j]==n){
                    sum++;
                }
            }
        }
        printf("%d\n",sum);
    }
    return 0;
}

问题 C: Goldbach's Conjecture

标签：output   actual   ati   numbers   ports   exist   tput   cond   gre