## 686 - Goldbach's Conjecture (II)

All about problems in Volume 6. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

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
Location: Bangladesh
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
Location: (BUBT) Dhaka,Bagladesh.

### 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
Location: Dhaka, Bangladesh
Contact:

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

Why I am getting Runtime error? please help me
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
Location: Dhaka, Bangladesh
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!

Find us on Facebook. Follow us on Twitter.

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!

Find us on Facebook. Follow us on Twitter.

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!

Find us on Facebook. Follow us on Twitter.