## 686 - Goldbach's Conjecture (II)

Moderator: Board moderators

Ming Han
Learning poster
Posts: 77
Joined: Thu Jun 06, 2002 7:10 pm
Location: Singapore
Contact:

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

ACM 686: Goldbach's Conjecture (II)

[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

xenon
Learning poster
Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland
won't give it away. are you shure you're considering all primes?

Ming Han
Learning poster
Posts: 77
Joined: Thu Jun 06, 2002 7:10 pm
Location: Singapore
Contact:

### All Primes

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

xenon
Learning poster
Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland
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...

Ming Han
Learning poster
Posts: 77
Joined: Thu Jun 06, 2002 7:10 pm
Location: Singapore
Contact:

### Thanks alot!

Thank You for your help. I forgot about the number 4.

Thanks again. Have a nice day. Yours Sincerly,
Ming Han

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am
for n = 4 your output should be 1 not 0.

Code: Select all

``````Input:
4

Output:
1``````
Try to precalculating the prime numbers and store it somewhere.

Hope it helps.   Regards,
RED SCORPION  lendlice
New poster
Posts: 22
Joined: Thu Nov 21, 2002 10:50 am

### 686 W.A

I got W.A
Anyone can help me
[cpp]//686
#include<stdio.h>
#include<math.h>
long primestack;
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]

duaxorms
New poster
Posts: 5
Joined: Sat Jul 05, 2003 7:53 am
Location: Korea
Contact:

### 686 :: Goldbach's Conjecture

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

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
But 10 also = 5 + 5!!

and 1 is not prime!
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

duaxorms
New poster
Posts: 5
Joined: Sat Jul 05, 2003 7:53 am
Location: Korea
Contact:
Observer wrote:But 10 also = 5 + 5!!

and 1 is not prime!
you are right...
thank you thank you~

dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

### re: 686 W.A

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

You later assume that primestack[n]>=in
and forget the case where you break the
loop because n==num-1

Pier
New poster
Posts: 38
Joined: Thu Mar 27, 2003 9:12 pm
Location: Aguascalientes, Mexico
Contact:
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:= false; num:= true;
for i:= 3 to ult_num do
if odd(i) then num:= true
else num:= false;
p:= 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);
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);
end;
End.
[/pascal]
There are 10 kind of people on this world: those who understand binary and those who don't!

Pier
New poster
Posts: 38
Joined: Thu Mar 27, 2003 9:12 pm
Location: Aguascalientes, Mexico
Contact:
Could some give me some test, please?
There are 10 kind of people on this world: those who understand binary and those who don't!

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
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.

Pier
New poster
Posts: 38
Joined: Thu Mar 27, 2003 9:12 pm
Location: Aguascalientes, Mexico
Contact:
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).
There are 10 kind of people on this world: those who understand binary and those who don't!