543 - Goldbach's Conjecture

[Sayeef]

HI,

I think you should generate prim numbers first and keep them in a array.
you only need to generate upto sqrt(1000000).And then substarct smallest primes from the number given and cheak wheather the ans is prime or not.

Sayeef

[bishop]

Code: Select all

plz help 
&& let me know this runtime error

X code deleted

[mmonish]

I don't find any coz of getting RE. But u may get WA.

Try this case
Input
6

Output
6 = 3 + 3

better u may resubmit it && check what's the actual error.
Hope it helps.

[bishop]

yaa

sorry for wrong inf

but i got "accepted"
by checking your output



Thank you..............................

[hridoy]

Why I am gettling TLE(acm-543), any help..

#include<stdio.h>
#include<math.h>
long prime(long n)
{
long i,z=1;
for(i=2;i<n/2;i++)
{
if(n%i==0)
{
z=0;
break;
}
}
if(z==1)
return 1;
else
return 0;
}
main()
{
long n,k,i,j,l,m,a[10000]={0};
while(1)
{
scanf("%ld",&n);
if(n==0)
break;
for(i=3,j=0;i<=n;i++)
{
if(prime(i))
{
a[j]=i;
j++;
}
}
k=0; l=0; m=0;
for(i=0;a!=0;i++)
{
for(j=0;a[j]!=0;j+=2)
{
if(n==(a+a[j])&&labs(l-m)<=labs(a-a[j]))
{
l=a;
m=a[j];
k=1;
}
}
}
if(k==1)
printf("%ld = %ld + %ld\n",n,l,m);
else
printf("Goldbach's conjecture is wrong.\n");
}
}

[Jan]

Your prime generator is way to slow. Just think that do you really have to divide upto n/2, or upto sqrt(n)?

And there are faster methods to calculate primes, like sieve method.

P.S. Use code tags to post a code.

[abhiramn]

Code: Select all

#include<stdio.h>
#include<math.h>
unsigned int primes[500000]={2,3,5};
int main()
{
	unsigned int i=7,k=2,n,flag,j,max,sum,x=1;
	while(i<=1000000)
	{
		n=sqrt(i);
		flag=1;
		for(j=0;primes[j]<=n;++j)
			if(i%primes[j]==0)
			{
				flag=0;
				break;
			}
		if(flag)
			primes[++k]=i;
		if(x)
			i+=4;
		else
			i+=2;
		x^=1;
	}
	while(1)
	{
		scanf("%u",&n);
		if(!n)
			break;
		if(n/2<k)
			max=n/2;
		else
			max=k;
		i=0;
		flag=1;
		while(max>=i)
		{
			sum=primes[max]+primes[i];
			if(sum==n)
			{
				printf("%u = %u + %u\n",n,primes[i],primes[max]);
				flag=0;
				break;
			}
			else if(sum<n)
				++i;
			else
				--max;
		}
		if(flag)
			printf("Goldbach's conjecture is wrong.\n");
	}
	return 0;
}

I have done all sorts of optimization possible. But still this is giving TLE. And when I run it on my system, it produces real fast output. Where am I going wrong?????

[abhiramn]

Guys! PLEASE HELP!!!!!!!!!!!!!!!!

[abhiramn]

I have done all I can about that program. Still Judge refuses to accept.

[abhiramn]

I modified the prime number generator. I am using a sieve now. But still no change. TLE

Code: Select all

#include<stdio.h>
unsigned int primes[785000],flags[1000002];
int main()
{
	unsigned int i,pind=-1,n,sum,start,end,j;
	for(i=0;i<=1000000;flags[i]=1,i++);
	for(i=2;i<=1000000;i++)
		if(flags[i])
		{
			primes[++pind]=i;
			flags[i]=0;
			for(j=i*i;j<=1000000;flags[j]=0,j+=i);
		}
	while(scanf("%u",&n)==1&&n)
	{
		if(n/2<pind)
			end=n/2;
		else
			end=pind;
		start=0;
		while(end>=start)
		{
			sum=primes[end]+primes[start];
			if(sum==n)
			{
				printf("%u = %u + %u\n",n,primes[start],primes[end]);
				break;
			}
			else if(sum<n)
				++start;
			else
				--end;
		}
	}
	return 0;
}

Please please suggest something. I have tried extremely large input files. Even then, this program runs super fast. PLEASE HELP!

[Jan]

Use binary search to find 'pind'. When cases like 80000, you start searching from the end of the array.

Try to be patient. You are spoiling the board. No one would reply if you do like that.

[mf]

Maybe try to change the part of your program, solving a test case, to for example:

Code: Select all

for a = 3, 5, 7, ... {
  if (a is prime and n-a is prime) {
    output that n is sum of a and (n-a);
    break;
  }
}

Most of the time the right a is very small, and so the code works very fast.

[shimon]

my code is given below.

#include<stdio.h>

int isPrime(long n)
{
if(n==1)
{
return 0;
}
if(n==2)
{
return 1;

}
if(n%2==0)
{
return 0;
}
int i;
for(i=3;(long)i*i<=n;i+=2 )
{
if(n%i==0)
return 0;
}
return 1;

}

int main(void)
{
long i,count;
long arr[100000];
while(1)
{
scanf("%ld",&count);
long primecounter=0;
if(count!=0)
{
for(i=3;i<=count;i++)
{
if(isPrime(i)==1)
{
arr[primecounter]=i;
primecounter++;
}
}

/*find out the pairs*/
long k;
for(k=0;k<primecounter;k++)
{
long temp,count1;
temp=arr[k];
count1=count-temp;
if(isPrime(count1))
{
printf("%d = %d + %d\n",count,temp,count1);
break;
}
}
}
else
{
break;
}
}
return 0;
}

i can not understand the reason that i am getting TLE. is it because i am using a function calling to get the primes??? plz help!

[Sohel_Cuet]

Hi shimon you should rather precalculate all primes instead of using your Isprime() so many times.You can use sieve method to determine all primes before you start taking input.Then just check through only the prime nubers.I hope it will work. Good Luck.

[sapnil]

To shimon

>> At first calculate all primes <1000000 (Using sieve)
Then the isPrime function will be

Code: Select all

int isPrime(long n)
{
long i,root;
root=sqrt(n);
for(i=0;prime[i]<=root;i++)
{
     if(n%prime[i]==0)
    {
           return 0;
    }
}

return 1;
}

Thanks
Keep posting
Sapnil