1259: Goldbach`s Conjecture

Problem Link

Hints:

store prime numbers in an vector;

then check the n-*it is prime or not

for example

6

2 4

3 3

here 2 is prime but (6-2)=4 is not prime

in the case of  3+3 here 3 is a prime and n-3=3 is also a prime number

 

 

 

View Code

#include<bits/stdc++.h>
using namespace std;
const int N=10000005;
bool status[N];
#define ll long long
vectorprime;

void sieve()
{
memset(status,0,sizeof status);
status[0]=status[1]=1;
ll k=N/2;

for(ll i=2;i<=k;i++)
{
if(!status[i])
{
prime.push_back(i);
for(ll j=2*i;j<=N;j+=i) status[j]=1; } } } int main() { sieve(); ll t,n,co=0,cs=1; //ll dp[N]; cin>>t;
while(t–)
{
cin>>n;

co=0;
ll k=n/2;
for(vector::iterator it=prime.begin();it!=prime.end() && *it<=k;it++)
{
if(status[n-*it]==0)
co++;
}
printf(“Case %lld: %lld\n”,cs++,co);
}
}

 

Advertisements

About waprogramming

I am in CSE,from CUET
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s