686 - Goldbach's Conjecture (II)

All about problems in Volume 6. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

686 - Goldbach's Conjecture (II)

Post by Ming Han » Tue Jun 11, 2002 4:29 pm

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

Post by xenon » Tue Jun 11, 2002 5:01 pm

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

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

All Primes

Post by Ming Han » Tue Jun 11, 2002 5:55 pm

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

Post by xenon » Tue Jun 11, 2002 8:04 pm

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

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

Thanks alot!

Post by Ming Han » Wed Jun 12, 2002 11:52 am

Thank You for your help. :D

I forgot about the number 4.

Thanks again. :lol:
Have a nice day. :)

Yours Sincerly,
Ming Han

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Post by Red Scorpion » Wed Mar 12, 2003 5:16 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. :lol: :lol: :lol:

Regards,
RED SCORPION :lol: :lol:

lendlice
New poster
Posts: 22
Joined: Thu Nov 21, 2002 10:50 am

686 W.A

Post by lendlice » Fri Jun 13, 2003 3:05 am

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
New poster
Posts: 5
Joined: Sat Jul 05, 2003 7:53 am
Location: Korea
Contact:

686 :: Goldbach's Conjecture

Post by duaxorms » Sat Jul 05, 2003 8:01 am

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

Post by Observer » Sat Jul 05, 2003 8:07 am

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:

Post by duaxorms » Sat Jul 05, 2003 8:46 am

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

and 1 is not prime!
you are right...
thank you :lol:

i had mistake..

thank you~

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

re: 686 W.A

Post by dumb dan » Tue Aug 05, 2003 1:10 am

> 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

User avatar
Pier
New poster
Posts: 38
Joined: Thu Mar 27, 2003 9:12 pm
Location: Aguascalientes, Mexico
Contact:

Post by Pier » Sun Jan 04, 2004 5:10 am

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]
There are 10 kind of people on this world: those who understand binary and those who don't!

User avatar
Pier
New poster
Posts: 38
Joined: Thu Mar 27, 2003 9:12 pm
Location: Aguascalientes, Mexico
Contact:

Post by Pier » Thu Jan 22, 2004 2:52 am

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!

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Thu Jan 22, 2004 10:33 am

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.

User avatar
Pier
New poster
Posts: 38
Joined: Thu Mar 27, 2003 9:12 pm
Location: Aguascalientes, Mexico
Contact:

Post by Pier » Sat Jan 24, 2004 4:32 am

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!

Post Reply

Return to “Volume 6 (600-699)”