Page 3 of 3

### 686 WA

Posted: Thu Aug 17, 2006 2:08 pm
#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;
}

Posted: Fri Aug 18, 2006 10:13 am
I m not sure, but i think this code should get TLE not WA as ur generating primes all the time!!

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

Posted: Mon Apr 07, 2008 10:47 am
Thanks! Antonio Ocampo I also have a problem like that...
I was thinking about odd primes...
But it should be even & odd both...

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

Posted: Thu Jul 28, 2011 9:30 pm
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?

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

Posted: Thu Feb 02, 2012 10:14 pm
here is my code:

Code: Select all

``````#include <cstdio>
bool sieve[100000]={0};
unsigned long long prim[100000];
int main()
{
unsigned long long i,j,n, k=0;
sieve[0]=1; sieve[1]=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;
}

``````

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

Posted: Tue Feb 07, 2012 2:35 am
Seg fault for input 4.

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

Posted: Thu Feb 09, 2012 7:37 pm
Thanks a lot
Thanks a lot
Thanks a lot
Thanks a lot
Thanks a lot
Finally I got it aaaccc.

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

Posted: Tue Nov 19, 2013 10:48 pm
Input:

Code: Select all

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

Code: Select all

``````1
1
2
1
``````

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

Posted: Fri Apr 04, 2014 2:12 pm
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
``````

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

Posted: Wed Apr 23, 2014 4:38 am
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[32770],ps[3525];
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[0]=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;
}

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

Posted: Wed Apr 23, 2014 1:20 pm
ifti_khar,

Use code tags to make your code readable. It's tough to debug otherwise.

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

Posted: Wed Apr 23, 2014 1:31 pm
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.