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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

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

Code: Select all

generate a list of primes p
for(i = 0; ; i++)
break if you find n - p[i] in a binary search of p
Check input and AC output for thousands of problems on uDebug!

Yusif
New poster
Posts: 27
Joined: Tue Jun 25, 2013 2:24 am

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

Thanks, it worked.
But I cant see how it is faster; it is like O(n lgn) while mine was O(n)! brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

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

You can also get AC using two nested for loops like:

Code: Select all

void findGold (vi &a, int &x, int &y, int e){
for(x = 0; ; x++) {
for(y = x; y < a.size() && a[x] + a[y] < e; y++);
if(a[x] + a[y] == e)
return;
}
}
but it's not as fast as using binary search. Your original code iterates from both ends of the prime array so it's slower if the two primes are close together and small.
Last edited by brianfry713 on Fri Nov 01, 2013 7:56 pm, edited 3 times in total.
Check input and AC output for thousands of problems on uDebug!

Yusif
New poster
Posts: 27
Joined: Tue Jun 25, 2013 2:24 am

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

I added this to the beginning of the original findGold

Code: Select all

y= lower_bound(a.begin(), a.end(), e)-a.begin()+1;
if (y>=a.size())
y=a.size()-1;
and it got the best time among my submissions.

I guess the worst input for the original code was 6, because the answer is 3 + 3 and "y" was to iterate through the whole array,
but when I run it myself and enter 6 it outputs in no time! How is that?! brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

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

In my code, I generate 78,497 primes. I tested all possible inputs, on average the small prime is only in the 5.2 position, with an average value of 19.8
So the average number of iterations of the binary search code would be 5.2 * log2(78497) = 84.6 for any n value.
My guess is most of the judge's input is small n, and your original code would have to iterate from the end of the prime list almost to the front. For an n of 6 your original code is going to have around 78497 iterations.
Try testing the different versions of your code on an input file with many small n values and you should be able to see the difference in running time.
On some problems the average running time is more important than the worst case.
Check input and AC output for thousands of problems on uDebug!

Yusif
New poster
Posts: 27
Joined: Tue Jun 25, 2013 2:24 am

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

Let's make something clear,
I assume that the time is the maximum of every single testcase's running time.
Am I wrong?! Is it their sum? brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

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

There is one input file with many values for n. The run time is the sum of your programs time to print the output for all values of n in the input file.
Check input and AC output for thousands of problems on uDebug!

Yusif
New poster
Posts: 27
Joined: Tue Jun 25, 2013 2:24 am

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

Well then, it explains how.
Thanks again!

fay007
New poster
Posts: 1
Joined: Thu Mar 27, 2014 10:54 am

543

getting TLE!! what is the wrong

Code: Select all

#include<iostream>
#include<stdio.h>
#include<cmath>

using namespace std;

long int num1;
long int num2;
long int g=0;
bool prime_num;
long calculate_prime(long int p)
{

for(long int k=4;k<=p;k+=2)
{
prime_num[k]=true;
}
for(long int i=3;i<=(int)sqrt(p);i+=2)
{

for(long int k=(i*i);k<=p;k+=2*i)
{
prime_num[k]=true;
}

}

for(long int i=2;i<p;i++)
{
if(prime_num[i]==false && prime_num[p-i]==false)
{

num2=i;
num1=p-i;
g++;
break;

}

}

}

void show(int p)
{

if(g==0)
{
printf("Goldbach's conjecture is wrong. \n");
}
else
{
printf("%d = %d + %d\n",p,num2,num1);
g=0;
}

}

int main()
{
long int p;
while(scanf("%d",&p)==1)
{
if(p==0)
break;
else
{
calculate_prime(p);
show(p);
}

}

return 0;

}

uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

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

Bluefin wrote:I do not look throught your code, but my algorithm is like this:

(1) use sieve of Eratosthnenes to find all the prime numbers up tp 1000000

(2) add the smallest prime number and the largest prime number which is smaller than n

(3) if the sum is equal to n, print them, else continue step 2
Thanks for sharing. This is the approach that was the most clear to me - especially since I know that the code I wrote when I first thought of this would result in a TL.

Here's some input / output that I found useful during testing / debugging.

Input:

Code: Select all

999968
6
568
43422
989838
46
10
999998
748386
8
0
Output:

Code: Select all

999968 = 7 + 999961
6 = 3 + 3
568 = 5 + 563
43422 = 11 + 43411
989838 = 7 + 989831
46 = 3 + 43
10 = 3 + 7
999998 = 19 + 999979
748386 = 7 + 748379
8 = 3 + 5
Check input and AC output for over 7,500 problems on uDebug!

New poster
Posts: 29
Joined: Wed Jun 18, 2014 3:57 pm

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

i got wa.here is my code...

Code: Select all

#include<stdio.h>
#include<math.h>
int p(int n);
int main(void)
{
int n;
while(scanf("%d",&n)!=EOF)
{
int i=0;
if(n==0) return 0;
if(n>=6 && n<1000000)
{

int as=1;
for(i=3;i<=(int)sqrt(n)+1;i=i+2)
{
int k=0;
int j=p(i);
if(j==2)
{
k=p(n-i);
if(k==2)
{
printf("%d = %d + %d\n",n,i,n-i);
as=0;
break;
}

}
}
if(as==1) printf("Goldbach\'s conjecture is wrong.\n");
}
}
return 0;
}
int p(int n)
{
int i;
int flag=3;
for(i=2;i<=(int)sqrt(n)+1;i=i+1)
{
if(n%i==0)
{
flag=0;
return 3;
break;
}
}
if(flag!=0&&n>1)
{
return 2;
}
else if(n<=1)
{
return 3;
}
}
]
Last edited by brianfry713 on Tue Nov 18, 2014 9:30 pm, edited 1 time in total.
Reason: Added code blocks

uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

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

sampad74 wrote:i got wa.here is my code...
Right. So if you're sharing code and do use code tags at least make sure they're actually being used. How legible do you think your code looks in the post above?

Also, try putting in the statement

Code: Select all

return 0;
at the end of your main function.
Check input and AC output for over 7,500 problems on uDebug!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

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

brianfry713 wrote:

Code: Select all

generate a list of primes p
for(i = 0; ; i++)
break if you find n - p[i] in a binary search of p
308 = 31 + 277
Check input and AC output for thousands of problems on uDebug!

Helaluddin_brur
New poster
Posts: 15
Joined: Tue Oct 21, 2014 4:08 pm
Contact:

Re: 543 - Goldbach's Conjecture

Why I am getting time limit
here is my code

Code: Select all

#include<stdio.h>
#include<math.h>
int p;
int h;
int prime(int n)
{
int i=0,j=0,k=0,m=0;

for(i=2;i<n;i++)
{
m=0;
for(j=2;j<i;j++)
{
if(i%j==0)
{
m++;
break;
}
}
if(m==0)
{
p[k]=i;
k++;
}
}
}
int main()
{
int i,j,n,a=0,b=0;
//freopen("63f.txt","r",stdin);
while(scanf("%d",&n)==1)
{
if(n==0)
break;
a=0,b=0;
if(n%2==0)
{
prime(n);
i=0;
while(p[i])
{
//printf("%d ",p[i]);
i++;
}
h=i;
for(i=0;i<h;i++)
{
for(j=h-1;j>=0;j--)
{
if(p[i]+p[j]==n)
{
a=p[j];
b=p[i];
break;
}
}
}
}

if(a>0&&b>0)
{
printf("%d = %d + %d\n",n,a,b);
}
else
printf("Goldbach's conjecture is wrong.\n");
}
return 0;
}
Last edited by brianfry713 on Tue Nov 18, 2014 9:30 pm, edited 1 time in total.
Reason: Added code blocks

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

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

brianfry713 wrote:

Code: Select all

generate a list of primes p
for(i = 0; ; i++)
break if you find n - p[i] in a binary search of p
Check input and AC output for thousands of problems on uDebug!