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

Moderator: Board moderators

To artem:

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`
Last edited by georgemouse on Tue Jan 31, 2006 4:06 pm, edited 1 time in total.
georgemouse
New poster

Posts: 13
Joined: Sun Aug 28, 2005 3:39 pm
Location: Taiwan

To artem:
Thank you!!!
I have accepted!!!!
georgemouse
New poster

Posts: 13
Joined: Sun Aug 28, 2005 3:39 pm
Location: Taiwan

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

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....
Ami ekhono shopno dekhi...
HomePage
Jan
Guru

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm

543 why WA pls help

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:

}

}
ishtiaq ahmed
Learning poster

Posts: 53
Joined: Sat Jul 29, 2006 7:33 am

hey!

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
Experienced poster

Posts: 162
Joined: Thu Jul 13, 2006 7:07 am

always try to avoid using goto function.

newton
Experienced poster

Posts: 162
Joined: Thu Jul 13, 2006 7:07 am

thanx
ishtiaq ahmed
Learning poster

Posts: 53
Joined: Sat Jul 29, 2006 7:33 am

543

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

#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();
}
samiullah
md.samiullah[sami]
New poster

Posts: 1
Joined: Sun Aug 27, 2006 11:00 am

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 !!
"It's nice to be important, but it's more important to be nice"

http://bluefintuna.wordpress.com/
Bluefin
New poster

Posts: 20
Joined: Sat Jul 08, 2006 3:39 pm

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
Sayeef
New poster

Posts: 12
Joined: Sun Jun 18, 2006 3:06 am

543 golbach's conjecture RE

[code]
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.
bishop
New poster

Posts: 43
Joined: Fri May 04, 2007 12:57 pm

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.
mmonish
Experienced poster

Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

yaa

sorry for wrong inf

but i got "accepted"

Thank you..............................
bishop
New poster

Posts: 43
Joined: Fri May 04, 2007 12:57 pm

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[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");
}
}
hridoy
New poster

Posts: 21
Joined: Tue May 08, 2007 10:30 am
Location: Dhaka

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
Jan
Guru

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm