## 686 - Goldbach's Conjecture (II)

Moderator: Board moderators

Tahasin
New poster
Posts: 6
Joined: Tue Jun 27, 2006 7:19 am

### 686 WA

#include<stdio.h>
#include<math.h>
#define p 10000
main()
{
int a,c[p],i,j,prime,count,counter;
while((scanf("%d",&a))==1)
{
if(a==0)break;
count=0;counter=0;
for(i=2;i<=a;i++)
{
prime=1;
for(j=2;j<=sqrt(i);j++)if(i%j==0)prime=0;
if(prime){c[count]=i;count++;}
}
for(i=0;i<count;i++)
{
for(j=i;j<count;j++)if((c+c[j])==a)counter++;
}
printf("%d\n",counter);
}
return 0;
}

A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm
I m not sure, but i think this code should get TLE not WA as ur generating primes all the time!!

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

### Re: 686:Goldbach's Conjecture (II) WHY WRONG ANSWER?????

Thanks! Antonio Ocampo I also have a problem like that...
I was thinking about odd primes...
But it should be even & odd both...
try_try_try_try_&&&_try@try.com
This may be the address of success.

plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

### Re: 686 - Goldbach's Conjecture (II)

This is quite funny for sure. I tried for more than one week, trying to prepare a tedious algorithm for this problem. I tried so hard but in vain. I tried using Eratosthenes Sieve, Yarin Sieve, DP, cycle finding and many other things but still couldn't find an effective algorithm to solve this problem. At last I concluded that it is impossible to solve this. However, I was dumbfounded because many users managed to solve this in 0.000 seconds. I was saying wtf? They have the judge input data or what because noway this is possible. It was after one week of hard-work I realized that the inputs are less than 2^15 and not 10^15   Just out of curiosity, is it possible to solve this problem within the given time limit if the maximum limit is 10^15 instead of 2^15?
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

uvasarker
Learning poster
Posts: 96
Joined: Tue Jul 19, 2011 12:19 pm
Contact:

### Re: 686 - Goldbach's Conjecture (II)

here is my code:

Code: Select all

``````#include <cstdio>
bool sieve={0};
unsigned long long prim;
int main()
{
unsigned long long i,j,n, k=0;
sieve=1; sieve=1;  // 1 = non-prime
for(i=4 ; i<=40000 ; i+=2) sieve[i]=1;
for(i=3 ; i<40000 ; i+=2)
{
if(sieve[i]==0)
{
for(j=i*i ; j<=41000 ; j+=2*i)
sieve[j]=1;
}
}

for(i=2 ; i<=32768 ; i++)
{
if(sieve[i]==0)
{
prim[k]=i;
k++;
}
}

while(scanf("%llu",&n)==1 && n!=0)
{
unsigned long long I,J,tmp=n/2, s, p=0;
for(I=n-1 ; I>=tmp-1 ; I-=2)
{
if(sieve[I]==0)
{
for(J=2 ; J<=tmp ; J++)
{
if(sieve[J]==0)
{
s=I+J;
if(s==n)
p++;
}
}
}
}
printf("%llu\n",p);
}

return 0;
}

``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 686 - Goldbach's Conjecture (II)

Seg fault for input 4.
Check input and AC output for thousands of problems on uDebug!

uvasarker
Learning poster
Posts: 96
Joined: Tue Jul 19, 2011 12:19 pm
Contact:

### Re: 686 - Goldbach's Conjecture (II)

Thanks a lot
Thanks a lot
Thanks a lot
Thanks a lot
Thanks a lot
Finally I got it aaaccc.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 686 - Goldbach's Conjecture (II)

Input:

Code: Select all

``````4
6
10
12
0
``````
AC output:

Code: Select all

``````1
1
2
1
``````
Check input and AC output for thousands of problems on uDebug!

uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

### Re: 686 - Goldbach's Conjecture (II)

Here's some input / output I found useful during testing / debugging.

Input:

Code: Select all

``````1000
32766
22824
32664
32266
88
23232
0``````
AC Output:

Code: Select all

``````28
518
377
498
289
4
428
``````
Check input and AC output for over 7,500 problems on uDebug!

ifti_khar
New poster
Posts: 1
Joined: Wed Apr 23, 2014 4:32 am

### Re: 686 - Goldbach's Conjecture (II)

WA : 686 - Goldbach's Conjecture (II)
my program give correct ans but judge WA my code is below

#include<bits/stdc++.h>
using namespace std;
int p,ps;
int a,b,c,d,i,j,k,l,m,h,r,q,sr,e;

int main()
{
//freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
for(i=3;i<=32768;i+=2)
p=0;
ps=2;
j=1;
sr=sqrt(32768);
for(i=3;i<=sr;i+=2)
{
if(p==0)
{
ps[j]=i;
j++;
for(k=i*i;k<=32768;k+=i+i)
p[k]=1;
}
}
for(;i<=32768;i+=2)
{
if(p==0)
{
ps[j]=i;
j++;
}
}
a=j-1;
while(cin>>b)
{
if(b==0)
break;
else if(b==4)
cout<<"1\n";
else
{
b=b--;
e=0;
for(r=b;r>=5;r-=2)
{
l=0;
h=a;
for(q=0;q<100;q++)
{
m=(l+h)/2;
if(r==ps[m]||l>h)
break;
else if(r<ps[m])
h=m-1;
else
l=m+1;
}
if(l>h)
continue;
else
break;
}
d=1;
b++;
e=0;
while(1)
{
if(d>m)
break;
if(ps[m]+ps[d]==b)
{
e++;
d++;
}
else if(ps[m]+ps[d]<b)
d++;
else
m--;
}
cout<<e<<"\n";
}

}
return 0;
}

uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

### Re: 686 - Goldbach's Conjecture (II)

ifti_khar,

Use code tags to make your code readable. It's tough to debug otherwise.
Check input and AC output for over 7,500 problems on uDebug!

uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

### Re: 686 - Goldbach's Conjecture (II)

ifti_khar wrote:my program give correct ans but judge WA my code is below
Change the following line to

Code: Select all

``b=b--;``
to

Code: Select all

``b--;``
I did this and submitted your code and got AC.
Check input and AC output for over 7,500 problems on uDebug!