543 - Goldbach's Conjecture

[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;
}

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

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

[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

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

[Sajid]

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]

[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

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

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

[Riyad]

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

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

[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

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

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

[horape]

* 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