OJ Board

Posted: **Mon Sep 04, 2006 2:51 am**

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

Posted: **Wed May 23, 2007 10:03 am**

Code: Select all

plz help 
&& let me know this runtime error

X code deleted

Posted: **Wed May 23, 2007 3:25 pm**

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.

Posted: **Thu May 24, 2007 6:29 pm**

yaa

sorry for wrong inf

but i got "accepted"
by checking your output

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

Posted: **Sat Jun 02, 2007 11:18 am**

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");
}
}

Posted: **Sat Jun 02, 2007 5:15 pm**

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.

Posted: **Thu Jun 21, 2007 8:14 pm**

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

Posted: **Fri Jun 22, 2007 9:48 am**

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

Posted: **Fri Jun 22, 2007 8:27 pm**

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

Posted: **Sat Jun 23, 2007 9:48 pm**

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!

Posted: **Sat Jun 23, 2007 10:01 pm**

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.

Posted: **Sat Jun 23, 2007 10:04 pm**

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.

Posted: **Sun Aug 26, 2007 3:08 pm**

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!

Posted: **Sun Sep 02, 2007 11:10 pm**

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.

Posted: **Wed Oct 17, 2007 2:21 pm**

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

OJ Board

543 - Goldbach's Conjecture

543 golbach's conjecture RE

TLE acm-543

TLE

MORE TLE

543-goldbach's conjecture..WHY AM I GETTING TLE??