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

bishop
New poster
Posts: 43
Joined: Fri May 04, 2007 12:57 pm

543 golbach's conjecture RE

Post by bishop » Wed May 23, 2007 10:03 am

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

bishop
New poster
Posts: 43
Joined: Fri May 04, 2007 12:57 pm

Post by bishop » Thu May 24, 2007 6:29 pm

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

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

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

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

TLE

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

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

Post by abhiramn » Fri Jun 22, 2007 9:48 am

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 » Fri Jun 22, 2007 8:27 pm

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 » Sat Jun 23, 2007 9:48 pm

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

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

Sohel_Cuet
New poster
Posts: 4
Joined: Thu Nov 24, 2005 5:47 am
Location: Bangladesh
Contact:

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

@@@ Jony @@@

Post Reply

Return to “Volume 5 (500-599)”