Page **3** of **3**

### 686 WA

Posted: **Thu Aug 17, 2006 2:08 pm**

by **Tahasin**

#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**

by **A1**

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**

by **Obaida**

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**

by **plamplam**

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**

by **uvasarker**

Why I am getting Runtime error? please help me

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**

by **brianfry713**

Seg fault for input 4.

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

Posted: **Thu Feb 09, 2012 7:37 pm**

by **uvasarker**

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**

by **brianfry713**

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

Posted: **Fri Apr 04, 2014 2:12 pm**

by **uDebug**

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:

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

Posted: **Wed Apr 23, 2014 4:38 am**

by **ifti_khar**

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**

by **uDebug**

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**

by **uDebug**

ifti_khar wrote:my program give correct ans but judge WA my code is below

Change the following line to

to

I did this and submitted your code and got AC.