686 - Goldbach's Conjecture (II)

[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

[xenon]

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

[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

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

[Ming Han]

Thank You for your help.

I forgot about the number 4.

Thanks again.
Have a nice day.

Yours Sincerly,
Ming Han

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

Regards,
RED SCORPION

[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]

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

[Observer]

But 10 also = 5 + 5!!

and 1 is not prime!

[duaxorms]

But 10 also = 5 + 5!!

and 1 is not prime!

you are right...
thank you

i had mistake..

thank you~

[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

[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]

[Pier]

Could some give me some test, please?

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

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