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

I forgot about the number 4.

Thanks again. :lol:
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.

Code: Select all

Input:
4

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

Hope it helps. :lol: :lol: :lol:

Regards,
RED SCORPION :lol: :lol:

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 :lol:

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