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

Sayeef
New poster
Posts: 12
Joined: Sun Jun 18, 2006 3:06 am

Post by 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
New poster
Posts: 43
Joined: Fri May 04, 2007 12:57 pm

543 golbach's conjecture RE

Post by bishop »

Code: Select all

plz help 
&& let me know this runtime error

X code deleted
Last edited by bishop on Thu May 24, 2007 6:29 pm, edited 1 time in total.

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Post by 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
New poster
Posts: 43
Joined: Fri May 04, 2007 12:57 pm

Post by bishop »

yaa

sorry for wrong inf

but i got "accepted"
by checking your output

:D

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

hridoy
New poster
Posts: 21
Joined: Tue May 08, 2007 10:30 am
Location: Dhaka
Contact:

TLE acm-543

Post by 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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by 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.
Ami ekhono shopno dekhi...
HomePage

abhiramn
New poster
Posts: 29
Joined: Sat May 26, 2007 7:54 pm

TLE

Post by 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????? :cry: :cry: :cry: :cry: :cry: :cry:

abhiramn
New poster
Posts: 29
Joined: Sat May 26, 2007 7:54 pm

Post by abhiramn »

Guys! PLEASE HELP!!!!!!!!!!!!!!!! :cry: :cry: :cry: :cry: :cry: :cry: :cry: :cry: :cry:

abhiramn
New poster
Posts: 29
Joined: Sat May 26, 2007 7:54 pm

Post by abhiramn »

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

abhiramn
New poster
Posts: 29
Joined: Sat May 26, 2007 7:54 pm

MORE TLE

Post by abhiramn »

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

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by 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.
Ami ekhono shopno dekhi...
HomePage

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by 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
New poster
Posts: 1
Joined: Sun Aug 26, 2007 2:56 pm

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

Post by 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
New poster
Posts: 4
Joined: Thu Nov 24, 2005 5:47 am
Location: Bangladesh
Contact:

Post by 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.:D
Keep dreaming.It costs nothing but makes you living

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:

Post by 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
"Dream Is The Key To Success"

@@@ Jony @@@

Post Reply

Return to “Volume 5 (500-599)”