686 - Goldbach's Conjecture (II)
Moderator: Board moderators
686 - Goldbach's Conjecture (II)
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
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
All Primes
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
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
Thanks alot!
Thank You for your help.
I forgot about the number 4.
Thanks again.
Have a nice day.
Yours Sincerly,
Ming Han
![:D](./images/smilies/icon_biggrin.gif)
I forgot about the number 4.
Thanks again.
![:lol:](./images/smilies/icon_lol.gif)
Have a nice day.
![:)](./images/smilies/icon_smile.gif)
Yours Sincerly,
Ming Han
-
- Experienced poster
- Posts: 192
- Joined: Sat Nov 30, 2002 5:14 am
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
![:lol:](./images/smilies/icon_lol.gif)
Code: Select all
Input:
4
Output:
1
Hope it helps.
![:lol:](./images/smilies/icon_lol.gif)
![:lol:](./images/smilies/icon_lol.gif)
![:lol:](./images/smilies/icon_lol.gif)
Regards,
RED SCORPION
![:lol:](./images/smilies/icon_lol.gif)
![:lol:](./images/smilies/icon_lol.gif)
686 W.A
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]
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
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..
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..
But 10 also = 5 + 5!!
and 1 is not prime!
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
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
re: 686 W.A
> 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
> 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
-
- 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[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]
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!
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
-
- 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).
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!