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

Post by brianfry713 » Wed Oct 30, 2013 9:27 pm

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

Post by Yusif » Thu Oct 31, 2013 1:22 am

Thanks, it worked.
But I cant see how it is faster; it is like O(n lgn) while mine was O(n)! :o

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

Post by brianfry713 » Thu Oct 31, 2013 8:44 pm

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

Post by Yusif » Fri Nov 01, 2013 12:08 am

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?! :roll:

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

Post by brianfry713 » Sat Nov 02, 2013 12:05 am

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

Post by Yusif » Sun Nov 03, 2013 1:01 am

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

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

Post by brianfry713 » Tue Nov 05, 2013 12:34 am

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

Post by Yusif » Tue Nov 05, 2013 10:36 pm

Well then, it explains how.
Thanks again!

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

543

Post by fay007 » Thu Mar 27, 2014 3:41 pm

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[1100002];
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;

    }



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

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

Post by uDebug » Thu Apr 17, 2014 2:34 pm

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!

Find us on Facebook. Follow us on Twitter.

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

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

Post by sampad74 » Fri Jun 27, 2014 4:23 pm

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;
        }
}
]
please..anyone help.
Last edited by brianfry713 on Tue Nov 18, 2014 9:30 pm, edited 1 time in total.
Reason: Added code blocks

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

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

Post by uDebug » Sat Jun 28, 2014 6:52 am

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!

Find us on Facebook. Follow us on Twitter.

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

Post by brianfry713 » Mon Jul 07, 2014 9:12 pm

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
Location: Bangladesh
Contact:

Re: 543 - Goldbach's Conjecture

Post by Helaluddin_brur » Tue Nov 18, 2014 7:01 am

Why I am getting time limit
any one please help me
here is my code

Code: Select all

#include<stdio.h>
#include<math.h>
int p[100000];
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??

Post by brianfry713 » Tue Nov 18, 2014 9:32 pm

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!

Post Reply

Return to “Volume 5 (500-599)”