543 - Goldbach's Conjecture

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

Moderator: Board moderators

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

543 - Goldbach's Conjecture

Post by zakaria » Thu Jun 27, 2002 11:43 pm

#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
Learning poster
Posts: 96
Joined: Mon Jun 24, 2002 1:22 pm
Location: Hungary
Contact:

Post by Picard » Fri Jun 28, 2002 9:13 am

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
New poster
Posts: 8
Joined: Mon Sep 29, 2003 3:13 pm

543 WA

Post by Admus » Fri Oct 10, 2003 8:50 pm

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.


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

543 why wa .......

Post by Riyad » Fri Oct 24, 2003 7:08 pm

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

Post by Maarten » Sun Oct 26, 2003 1:52 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

Post by Sajid » Sun Oct 26, 2003 2:43 pm

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)
Sajid Online: www.sajidonline.com

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

right u r

Post by Riyad » Sun Oct 26, 2003 3:41 pm

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

Post by Sajid » Sun Oct 26, 2003 3:53 pm

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
Location: CS, AIUB, Dhaka, Bangladesh
Contact:

Post by Tanzim-Saqib » Sun Oct 26, 2003 10:32 pm

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

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

hey thanx

Post by Riyad » Mon Oct 27, 2003 2:50 am

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
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

User avatar
Shaka_RDR
New poster
Posts: 23
Joined: Sat Oct 04, 2003 12:12 pm
Location: in Your Heart ^^
Contact:

Post by Shaka_RDR » Tue Oct 28, 2003 9:33 am

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

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

User avatar
Shaka_RDR
New poster
Posts: 23
Joined: Sat Oct 04, 2003 12:12 pm
Location: in Your Heart ^^
Contact:

Post by Shaka_RDR » Tue Oct 28, 2003 4:07 pm

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

Post by kiha » Mon Mar 01, 2004 9:50 pm

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

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

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

Post by horape » Fri Mar 05, 2004 3:02 pm

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

Post Reply

Return to “Volume 5 (500-599)”