543 - Goldbach's Conjecture

[brianfry713]

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

[Yusif]

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

[brianfry713]

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.

[Yusif]

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]

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.

[Yusif]

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]

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.

[Yusif]

Well then, it explains how.
Thanks again!

[fay007]

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;

    }

[uDebug]

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

[sampad74]

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.

[uDebug]

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.

[brianfry713]

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

[Helaluddin_brur]

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;
}

[brianfry713]

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