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

[georgemouse]

To artem:
Your code really works!!

But I still got TLE...........Why???
Is my method to find the pair of prime too slow?
I tried to modify my method to find the pair, but it seems no use.....

Can anyone tell me what's wrong in my code?

Code: Select all

 removed after AC

[georgemouse]

To artem:
Thank you!!!
I have accepted!!!!

[Jan]

I think your code is right. N>=6 So, there is no "Goldbach's conjecture is wrong.". And your printing is wrong...

Your code....

Code: Select all

     if(flag)
        printf("%llu = %llu +%llu\n",N,x,primal);

But it should be..

Code: Select all

     if(flag)
        printf("%llu = %llu + %llu\n",N,x,primal);

Missing one space....

[ishtiaq ahmed]

hi
i cannot understand why i am faced WA again and again. i have not found any errors.plz help me such for unexpected condition.
my code is
#include<stdio.h>
#include<math.h>
void main()
{
long long num,num1,j,k,i,flag,aa,cc;
while(scanf("%lld",&num)!=EOF)
{
if(num==0)
break;
j=3;
aa:
num1=num-j;
flag=1;
for(i=2;i<=sqrt(num1);i++)
{
flag=1;
if(num1%i==0)
{
flag=0;
break;
}
}
if(flag==1)
{
if(num1+j==num)
printf("%lld = %lld + %lld\n",num,j,num1);
}
if(flag==0)
{
j=j+2;
if(j>num1)
{
printf("Goldbach conjecture is wrong.\n");
goto cc;
}
goto aa;

}
cc:

}

}

[newton]

you can never get the unexpected condition. bcoz you are a modon!
----------newton

see the problem. there is the terminating condition is not EOF.
it is !=0.


best of luck.
bye

[newton]

always try to avoid using goto function.
bcoz it is bad programming.

[ishtiaq ahmed]

thanx

[md.samiullah[sami]]

i have tried to solve Goldbachs conjecture.
but there is a WR
i just cant understand why WR.my code is given below
any one please help me


#include<stdio.h>
#include<math.h>
//#include<conio.h>


main()
{
long long int i,j,n,index,flag,gb,p;
int prime[10]={3,5,7,11,13,17,19,23,29,31};
//clrscr();
/*prime[0] = 2;*///prime[0]=3;//index=1;
//printf("Enter Range:");
while(1)
{ //index=1;
scanf("%lld",&gb);
if(gb!=0)

{
for(i=0;i<=9;i++)
{ // p=0;
n=gb-prime[i];
flag=1;

for(j=3;j<=sqrt(n);j+=2)
if(n%j==0) //if(i%prime[j]==0)
{
flag=0;
break;
}
if(flag==1)
{
printf("%lld =%d + %lld",gb,prime[i],n);
p++;
break;
}
// else
// break;

// prime[index++] = i;
}
}

/*for(i=0;i<=10;i++)
{ for(j=index-2;j>=index-11;j--)
if((prime[i]+prime[j])==n)
{printf("%lld = %lld +%lld",n,prime[i],prime[j]);
break;}
if((prime[i]+prime[j])==n)
break;
} } */
else
break; }
//getch();
}

[Bluefin]

I've just solved this problem today !!
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

My ACC code cost about 0.8 second and used 1412 memory.
Not very efficient, but enough to solve this problem

Good luck !!

[Sayeef]

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]

[code]
plz help
&& let me know this runtime error

X code deleted

[mmonish]

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]

yaa

sorry for wrong inf

but i got "accepted"
by checking your output



Thank you..............................

[hridoy]

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[i]!=0;i++)
{
for(j=0;a[j]!=0;j+=2)
{
if(n==(a[i]+a[j])&&labs(l-m)<=labs(a[i]-a[j]))
{
l=a[i];
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]

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.