Page 1 of 8

543 - Goldbach's Conjecture

Posted: Thu Jun 27, 2002 11:43 pm
by zakaria
#include<iostream.h>
#include<math.h>

int main()
{


int prime[1000000]={0};
prime[2]=1;
prime[3]=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;
}

Posted: Fri Jun 28, 2002 9:13 am
by Picard
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...

543 WA

Posted: Fri Oct 10, 2003 8:50 pm
by Admus
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[1]:=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;
  readln(n);
  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;
      readln(n);
    end;
end.


543 why wa .......

Posted: Fri Oct 24, 2003 7:08 pm
by Riyad
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 PrimeNumber[MAX];
long int Count;
void GeneratePrime()
{
long int num,j;
PrimeNumber[0]=2;
PrimeNumber[1]=3;
PrimeNumber[2]=5;
PrimeNumber[3]=7;
Count=4;
for(num=11;num<MAX;num=num+2)
{
for(j=0;j<sqrt(PrimeNumber[Count-1]);j++)

if(num%PrimeNumber[j]==0)
break;

if(j==Count)
PrimeNumber[Count++]=num;
}
}


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++){

y=PrimeNumber;

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
Riyad

Posted: Sun Oct 26, 2003 1:52 pm
by Maarten
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??)

Check it

Posted: Sun Oct 26, 2003 2:43 pm
by Sajid
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 */
    PrimeNumber[Count++]=num;
You have to change your GeneratePrime( ) function. you have to check "j<=sqrt(PrimeNumber[Count-1])"

Change the code as follows:
[c] for(j=0,f=1;j<=sqrt(PrimeNumber[Count-1]);j++)

if(num%PrimeNumber[j]==0)
{
f=0;
break;
}
if(f) PrimeNumber[Count++]=num; [/c]
8)

right u r

Posted: Sun Oct 26, 2003 3:41 pm
by Riyad
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
Riyad

Posted: Sun Oct 26, 2003 3:53 pm
by Sajid
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...

Posted: Sun Oct 26, 2003 10:32 pm
by Tanzim-Saqib
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.

hey thanx

Posted: Mon Oct 27, 2003 2:50 am
by Riyad
hey thanx sajid and saqib :wink:
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 :P .
thanx once again

Posted: Tue Oct 28, 2003 9:33 am
by Shaka_RDR
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");
		}

	}

}



sorry for the messy code... please help me...[/c]

Posted: Tue Oct 28, 2003 12:27 pm
by Maarten
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

Posted: Tue Oct 28, 2003 4:07 pm
by Shaka_RDR
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 .... :D

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

Posted: Mon Mar 01, 2004 9:50 pm
by kiha
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 :P ?

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

Posted: Fri Mar 05, 2004 3:02 pm
by horape
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 :P ?
That's a really slow algorithm. Read on sieve.

Saludos,
HoraPe