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

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

Posted: **Tue Jun 11, 2002 4:29 pm**

by **Ming Han**

ACM 686: Goldbach's Conjecture (II)

I keep getting wrong answer.

[cpp]#include <stdio.h>

#include <math.h>

int prime(int num){

long root = int(sqrt(num));

if (num % 2 == 0) return 0;

for (int b=3; b<=root; b+=2)

if (num % b == 0) return 0;

return 1;

}

int main(){

unsigned int i,n,got;

while (scanf("%d",&n)==1){

if (n==0) break;

got = 0;

for (i=3;i<=(n/2);i+=2)

if ((prime(i) + prime(n-i))==2) got++;

printf("%d\n",got);

}

return 0;

}[/cpp]

Can somebody explain why I get wrong answer?

Thank You

Posted: **Tue Jun 11, 2002 5:01 pm**

by **xenon**

won't give it away. are you shure you're considering all primes?

### All Primes

Posted: **Tue Jun 11, 2002 5:55 pm**

by **Ming Han**

Just wondering if you had read the question.

I am not sure what you mean.

The question say: You may assume that each integer is even, and is greater than or equal to 4 and less than 2^15.

so, prime>=4, prime is odd.

Ming Han

Posted: **Tue Jun 11, 2002 8:04 pm**

by **xenon**

Sure I read the question, and solved the problem too.

Your conclusion is wrong; it says every integer in the input is even and >=4, it doesn't say every prime has to be odd.

Consider the simpelest case...

### Thanks alot!

Posted: **Wed Jun 12, 2002 11:52 am**

by **Ming Han**

Thank You for your help.

I forgot about the number 4.

Thanks again.

Have a nice day.

Yours Sincerly,

Ming Han

Posted: **Wed Mar 12, 2003 5:16 am**

by **Red Scorpion**

for n = 4 your output should be 1 not 0.

Try to precalculating the prime numbers and store it somewhere.

Hope it helps.

Regards,

RED SCORPION

### 686 W.A

Posted: **Fri Jun 13, 2003 3:05 am**

by **lendlice**

I got W.A

Anyone can help me

[cpp]//686

#include<stdio.h>

#include<math.h>

long primestack[50000];

int num=0;

long prime()

{

int i,j,tr=0;

for(i=2;i<=32768;i++)

{

for(j=2,tr=0;j<=sqrt(i);j++)

{

if(i%j==0)

{

tr=1;

break;

}

if(j>=3)

j++;

}

if(tr==0&&i!=0&&i!=1)

{

primestack[num]=i;

num++;

}

}

}

main()

{

long in,n=0,i=0,j=0,count=0;

prime();

while(scanf("%ld",&in)==1)

{

count=0;

if(in==0)

break;

while(primestack[n]<in&&n!=num-1)

n++;

for(i=0;i<n;i++)

{

for(j=n-1;j>=i;j--)

{

if(primestack*+primestack[j]==in)*

{

count++;

break;

}

}

}

printf("%ld\n",count);

}

}[/cpp]

### 686 :: Goldbach's Conjecture

Posted: **Sat Jul 05, 2003 8:01 am**

by **duaxorms**

sample input

6

10

12

0

sample output

1

2

1

i think sample output is wrong...

10 = 3 + 7.

12 = 1 + 11, 5 + 7.

so sample output is

1

1

2

Is this right?

sorry....i can't english well..

Posted: **Sat Jul 05, 2003 8:07 am**

by **Observer**

But 10 also = 5 + 5!!

and 1 is not prime!

Posted: **Sat Jul 05, 2003 8:46 am**

by **duaxorms**

Observer wrote:But 10 also = 5 + 5!!

and 1 is not prime!

you are right...

thank you

i had mistake..

thank you~

### re: 686 W.A

Posted: **Tue Aug 05, 2003 1:10 am**

by **dumb dan**

> while(primestack[n]<in&&n!=num-1)

> n++;

There is your problem.

You later assume that primestack[n]>=in

and forget the case where you break the

loop because n==num-1

Posted: **Sun Jan 04, 2004 5:10 am**

by **Pier**

Hi!

Can someone help me? I used almost the same code for the other Golbach problem and I got AC. I've also tried some test inputs I found and I get them correct.

Any help aprecciated!

[pascal]

Const

max= 1901;

ult_num= 32768;

Type

entero= longint;

primo = array [1..max] of entero;

lista = array [1..ult_num] of boolean;

Var

p: primo;

l: lista;

i,n,s: longint;

Procedure primos(var p: primo; var num: lista);

var

i,j,l,t: entero;

begin

num[1]:= false; num[2]:= true;

for i:= 3 to ult_num do

if odd(i) then num*:= true*

else num*:= false;*

p[1]:= 2; t:= 1;

i:= 3; l:= trunc(sqrt(ult_num));

While (i<= l) and (t<max) do

begin

if (num*) then*

begin

Inc(t);

p[t]:= i;

j:= i*i;

While (j<ult_num) do

begin

num[j]:= false;

Inc(j,2*i);

end;

end;

Inc(i,2);

end;

for i:= l to ult_num div 2 do

if num* then*

begin

Inc(t);

p[t]:= i;

end;

end;

Begin

primos(p,l);

readln(input,n);

While (n<>0) do

begin

s:= 0; i:= 1;

while (p*<= n div 2) do*

begin

if l[n-p*] then Inc(s);*

Inc(i);

end;

writeln(output,s);

readln(input,n);

end;

End.

[/pascal]

Posted: **Thu Jan 22, 2004 2:52 am**

by **Pier**

Could some give me some test, please?

Posted: **Thu Jan 22, 2004 10:33 am**

by **little joey**

Per:

You add the prime 181 (=sqrt(ult_num)) twice to your list of primes. This means your answer for every n for which (n-181) is prime is one too high.

For 22292 the correct answer is 177, but your program gives 178.

Posted: **Sat Jan 24, 2004 4:32 am**

by **Pier**

Thanks a lot! I finally got AC!

The funny thing is that I got AC on the other Golbach problem and it had the same mistake.

By the way, my name is Pier, not Per. (I think you might confused my name with Per Austrin, or maybe it's just a typo).