## 543 - Goldbach's Conjecture

Moderator: Board moderators

Sayeef
New poster
Posts: 12
Joined: Sun Jun 18, 2006 3:06 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

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

sorry for wrong inf

but i got "accepted" Thank you..............................

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

### TLE acm-543

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={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
Contact:
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

Code: Select all

``````#include<stdio.h>
#include<math.h>
unsigned int primes={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
New poster
Posts: 29
Joined: Sat May 26, 2007 7:54 pm
Guys! PLEASE HELP!!!!!!!!!!!!!!!!         abhiramn
New poster
Posts: 29
Joined: Sat May 26, 2007 7:54 pm
I have done all I can about that program. Still Judge refuses to accept.   abhiramn
New poster
Posts: 29
Joined: Sat May 26, 2007 7:54 pm

### MORE TLE

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,flags;
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;
}
``````

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

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;
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
Contact:
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. 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:
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 @@@