## 543 - Goldbach's Conjecture

Moderator: Board moderators

zakaria
New poster
Posts: 15
Joined: Thu Jun 27, 2002 11:34 pm

### 543 - Goldbach's Conjecture

#include<iostream.h>
#include<math.h>

int main()
{

int prime={0};
prime=1;
prime=1;
for(long k=5;k<1000000;k+=2)
{
int a=0;
for(long l=3;l<k;l+=2)
{
if(prime[l]==1)
{
if(k%l==0)
{
a=1;
break;
}

if(prime[l]>(long)(sqrt(k)+0.5))break;
}
}
if(a==0)prime[k]=1;
}

long n;
while(cin>>n&&n>0)
{
long a=0,b=0;
for(long m=3;m<=n/2;m+=2)
{
if(prime[m]==1)
{
long q=n-m;
if(prime[q]==1)
{
a=m;
b=q;
break;
}
}
}
if(a!=0&&b!=0)
cout<<n<<" = "<<a<<" + "<<b<<"\n";
else
cout<<"Goldbach's conjecture is wrong.\n";

}

return 0;
}

Picard
Learning poster
Posts: 96
Joined: Mon Jun 24, 2002 1:22 pm
Location: Hungary
Contact:
don't make so big arrays on the stack (in this case prime is 4Mb). make it a global variable. btw your prime searching algo is not effective for this problem, it's way too slow. try another algorithm, for example sieve http://www.fpx.de/fp/Software/Sieve.html. why use 'int' for a huge boolean array? it allocates 4x memory. btw there is another similar problem P10311...

New poster
Posts: 8
Joined: Mon Sep 29, 2003 3:13 pm

### 543 WA

Could help me? I don't know what's wrong with it?
or give me some input?

Code: Select all

``````var
tab:array[1..1000000]of longint;
wyn:array[1..50000]of byte;
n,a,nr,b:longint;
czy:boolean;
begin
tab:=2;
nr:=2;
fillchar(wyn,sizeof(wyn),0);
for a:=2 to 1000000 do
tab[a]:=maxlongint;
for a:=3 to 1000000 do
begin
b:=1;
czy:=true;
while tab[b]<=round(sqrt(a)) do
begin
if a mod tab[b]=0 then czy:=false;
inc(b);
end;
if czy then
begin
inc(wyn[a]);
tab[nr]:=a;
inc(nr);
end;
end;
while n<>0 do
begin
b:=2;
czy:=true;
while (tab[b]<=n div 2)and(czy) do
begin
if wyn[n-tab[b]]=1 then
begin
writeln(n,' ','=',' ',tab[b],' ','+',' ',n-tab[b]);
czy:=false;
end;
inc(b);
end;
if czy then
begin
write('Goldbach');
write(chr(39));
writeln('s conjecture is wrong.');
end;
end;
end.

``````

Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

### 543 why wa .......

i am having wa all the time in 543 . am i missing some thing ? my algorithm for this problem is verys easy .

1) generate prime according to the stipulated range .
2)start searching the array of primes like this .let a prime be "A" ,where prime=="A" and the number which is to be shown as the sum of two primes is "X".now check if "B" is prime . where B = X - A. if yes X=A +B.else i++;

here is my code . pliz check it for me .

[c]#include<stdio.h>
#include<math.h>
#define MAX 1000000
long int Count;
void GeneratePrime()
{
long int num,j;
Count=4;
for(num=11;num<MAX;num=num+2)
{

break;

if(j==Count)
}
}

int isPrime(long int n){

long int i ;
if(n==0L || n==1L)
return 0;
for(i=2;i<=sqrt(n);i++){

if((n%i)==0)
return 0;

else
continue;

}

return 1;

}

void GoldBachConjecture(long int x){

long int i;
long int y,z;
int flag,check;

check=0;

for(i=0;i<Count;i++){

if(y>x)
break;

z=x-y;

flag=isPrime(z);

if(flag==1){

printf("%ld = %ld + %ld\n",x,y,z);
check=1;
return;

}

else
continue;

}

if(check==0)

printf("Goldbach's conjecture is wrong.\n");

}

int main(){

long int x;
GeneratePrime();
while(scanf("%ld",&x)==1){
if(x==0L)
break;
GoldBachConjecture(x);
}
return 0;
}[/c]

plizzzz help me in this . i have tried many different things . but failed.
Bye
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm
Check your GeneratePrime() function... the only prime numbers it generates are 2,3,5,7.
Also, I am surprised you don't get TLE. Your method of generating primes and checking for primality is very inefficient. Have you ever heard of Erasthostenes Sieve (how the hell do you write it??)

Sajid
Learning poster
Posts: 94
Joined: Sat Oct 05, 2002 5:34 pm
Location: CS - AIUB, Dhaka, Bangladesh.
Contact:

### Check it

Maarten wrote:Also, I am surprised you don't get TLE. Your method of generating primes and checking for primality is very inefficient. Have you ever heard of Erasthostenes Sieve (how the hell do you write it??)
Maartin, I didn't use Sieve and it really doesn't matter in this problem, no chance to get TLE. (And also, you should not talk like this)

Riyad, your this condition never comes true, since you are not counting j 0 to count-1

Code: Select all

``````if(j==Count) /* Contradiction */
You have to change your GeneratePrime( ) function. you have to check "j<=sqrt(PrimeNumber[Count-1])"

Change the code as follows:

{
f=0;
break;
} Sajid Online: www.sajidonline.com

Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

### right u r

martin and sajid thanx to both of u for replying . yes i realised my mistake in the generating prime function . the function dont really stop . that means 2 3 5 7 are the only primes generated . i got tle in the problem 543 . my way of generating prime is really slow . i have faced this prob for a long time .(the need of an efficient algorithm for generating prime )can any one of u provide me a efficient algo for generating prime , if u people dont really face any prob.

**** sajid i made the correction u asked me to do . i did with no success . got TLE in the prob.
++++ martin , as a matter of regret i heard about the algorithm sieve of Erasthostenes. but i dont feel tempted to write one my self . and i also know how the algorithm works. thanx any way
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

Sajid
Learning poster
Posts: 94
Joined: Sat Oct 05, 2002 5:34 pm
Location: CS - AIUB, Dhaka, Bangladesh.
Contact:
Your GeneratePrimes() function seems ok, but u have to have faster IsPrime( ) function...
you are doing mod by all the numbers , but why ? and also even numbers you can mod with only prime numbers that is alreay in your PrimeNumber[ ] array.
GoldBachConjecture( ) function needs the same thing.

Try...
Sajid Online: www.sajidonline.com

Tanzim-Saqib
New poster
Posts: 10
Joined: Thu Jun 05, 2003 5:23 pm
Contact:
Have you ever heard of Erasthostenes Sieve (how the hell do you write it??)
What a way of talking!!!!

[c]int isPrime(unsigned long long p)
{
unsigned long long i;
for(i=2;i<=sqrt(p);i++)
if(!(p%i))
return 0;
return 1;
}[/c]

Trust me, this function is enough for this problem, whenever you need to check if a number is prime or not just call it. You don't even need to generate all the primes in an array. Anyway, I haven't seen your code yet.

Hope it helps.
[Tanzim Saqib]
-----------------------------
Problemsetter of 10490
Website: http://tanzim.tk

Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

### hey thanx

hey thanx sajid and saqib i did not realize how i could optimize my isPrime Function . but afetr readind u r post , i found out how to optimize it .

1)mod the number with the primes i generated (the fastest method)
2)mod the number with only odd numbers

i ll try to correct my code and let u people know what have happened .
thanx once again
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

Shaka_RDR
New poster
Posts: 23
Joined: Sat Oct 04, 2003 12:12 pm
Contact:
hi... can any body help me ?

i still got WA for 543... is there any tricky input ? i've checked my output with my friend's code (she got AC-ed) and its ok, here is my code :

Code: Select all

``````[c]
#include <stdio.h>
#include <math.h>

long angka;
long mulai;
int ok;

long genPrime(void)
{
long a;
long b;
long batas;
int prime;

for (a=mulai;;a+=2)
{
batas=sqrt(a)+1;
prime=1;
for (b=2;b<batas;b++)
{
if (a%b==0)
{
prime=0;
break;
}

}
if (prime==1) return a;
}

}

int isPrime(long cek)
{
long a;
long batas;
batas=sqrt(cek)+1;

for(a=2;a<batas;a++)
{
if (cek%a==0) return 0;
}

return 1;
}

void main()
{
long a1,a2;
#ifndef ONLINE_JUDGE
freopen ("543.in","r",stdin);
freopen ("543.out","w",stdout);
#endif

while (scanf ("%ld ",&angka)!=EOF)
{
if (angka==0) break;

mulai=3;
ok=0;
do
{
a1=genPrime();

if (a1>=angka) break;
a2=angka-a1;
ok=isPrime(a2);
mulai+=2;
}while (ok!=1);

if (ok==1)
{
printf ("%lld = %lld + %lld\n",angka,a1,a2);
}
else
{
printf ("Goldbach's conjecture is wrong.\n");
}

}

}

Every person exists for another person. and that person exists for the other one. it's just the matter of existence...
May every person helps each other and creates a world full of joy...

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm
If I'm correct, %lld is only used with long long data type. For long you should use %ld. Not sure if it matters though. For the rest I haven't been able to spot a mistake

Shaka_RDR
New poster
Posts: 23
Joined: Sat Oct 04, 2003 12:12 pm
Contact:
OH MY GOD !!!! you're right!!! i got AC now.... how can i be so careless ??? i have trace it for about 3 days and comparing 3MB sample input + 11 MB sample output manually...... and its... its just about %lld ....

btw, thanx a lot.... so this night i can sleep tight .... Every person exists for another person. and that person exists for the other one. it's just the matter of existence...
May every person helps each other and creates a world full of joy...

kiha
New poster
Posts: 37
Joined: Sat Dec 20, 2003 10:59 pm

### What's faster -- C/C++ or Pascal ?

Hi everybody,

I use Pascal OBVIOUSLY But ... trying to solve 543 - Goldbach's conjecture , I visited Steven Halim's website and it was written that I may store all primes in an array and do it with Brute Force [ if you know the problem ] . I did it [ in Pascal , I checked for every number lower than limit if it's prime * ] , and got TLE :/ Although it was written that this algorithm works ! Then I thought , C/C++ is faster than Pascal . Furthermore , when I look through the stats of some problems , rarely there is any person using Pascal within first ... er ... 10 times ? Usually , an algorithm implementated in C/C++ runs faster than the one in Pascal . Am I right ? If so , why is it like that ?

_____________________________________________________________
* Of course, for every n > 4 , I check if any prime i from 2 to sqrt (n) divides n , until I have found one that does or i have reached sqrt (n) -- can you think of any better algorithm ?
kiha

horape
New poster
Posts: 49
Joined: Sat Sep 13, 2003 3:18 pm
Location: Buenos Aires

### Re: What's faster -- C/C++ or Pascal ?

kiha wrote:* Of course, for every n > 4 , I check if any prime i from 2 to sqrt (n) divides n , until I have found one that does or i have reached sqrt (n) -- can you think of any better algorithm ?
That's a really slow algorithm. Read on sieve.

Saludos,
HoraPe