686 - Goldbach's Conjecture (II)

All about problems in Volume 6. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Tahasin
New poster
Posts: 6
Joined: Tue Jun 27, 2006 7:19 am

686 WA

Post by Tahasin » Thu Aug 17, 2006 2:08 pm

#include<stdio.h>
#include<math.h>
#define p 10000
main()
{
int a,c[p],i,j,prime,count,counter;
while((scanf("%d",&a))==1)
{
if(a==0)break;
count=0;counter=0;
for(i=2;i<=a;i++)
{
prime=1;
for(j=2;j<=sqrt(i);j++)if(i%j==0)prime=0;
if(prime){c[count]=i;count++;}
}
for(i=0;i<count;i++)
{
for(j=i;j<count;j++)if((c+c[j])==a)counter++;
}
printf("%d\n",counter);
}
return 0;
}

User avatar
A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm
Location: Bangladesh

Post by A1 » Fri Aug 18, 2006 10:13 am

I m not sure, but i think this code should get TLE not WA as ur generating primes all the time!!

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 686:Goldbach's Conjecture (II) WHY WRONG ANSWER?????

Post by Obaida » Mon Apr 07, 2008 10:47 am

Thanks! Antonio Ocampo I also have a problem like that...
I was thinking about odd primes...
But it should be even & odd both...
try_try_try_try_&&&_try@try.com
This may be the address of success.

User avatar
plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

Re: 686 - Goldbach's Conjecture (II)

Post by plamplam » Thu Jul 28, 2011 9:30 pm

This is quite funny for sure. I tried for more than one week, trying to prepare a tedious algorithm for this problem. I tried so hard but in vain. I tried using Eratosthenes Sieve, Yarin Sieve, DP, cycle finding and many other things but still couldn't find an effective algorithm to solve this problem. At last I concluded that it is impossible to solve this. However, I was dumbfounded because many users managed to solve this in 0.000 seconds. I was saying wtf? They have the judge input data or what because noway this is possible. It was after one week of hard-work I realized that the inputs are less than 2^15 and not 10^15 :( :-? :x

Just out of curiosity, is it possible to solve this problem within the given time limit if the maximum limit is 10^15 instead of 2^15?
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

uvasarker
Learning poster
Posts: 96
Joined: Tue Jul 19, 2011 12:19 pm
Location: Dhaka, Bangladesh
Contact:

Re: 686 - Goldbach's Conjecture (II)

Post by uvasarker » Thu Feb 02, 2012 10:14 pm

Why I am getting Runtime error? please help me
here is my code:

Code: Select all

#include <cstdio>
bool sieve[100000]={0};
unsigned long long prim[100000];
int main()
{
	unsigned long long i,j,n, k=0;
	sieve[0]=1; sieve[1]=1;  // 1 = non-prime
	for(i=4 ; i<=40000 ; i+=2) sieve[i]=1;
	for(i=3 ; i<40000 ; i+=2)
	{
		if(sieve[i]==0)
		{
			for(j=i*i ; j<=41000 ; j+=2*i)
				sieve[j]=1;
		}
	}
	
	for(i=2 ; i<=32768 ; i++)
	{
			if(sieve[i]==0)
			{
					prim[k]=i;
					k++;
			}
	}
	
	
	while(scanf("%llu",&n)==1 && n!=0)
	{
			unsigned long long I,J,tmp=n/2, s, p=0;
			for(I=n-1 ; I>=tmp-1 ; I-=2)
			{
					if(sieve[I]==0)
					{
							for(J=2 ; J<=tmp ; J++)
							{
									if(sieve[J]==0)
									{
											s=I+J;
											if(s==n)
												p++;
									}
							}
					}
			}
			printf("%llu\n",p);
	}
	
	return 0;
}


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

Re: 686 - Goldbach's Conjecture (II)

Post by brianfry713 » Tue Feb 07, 2012 2:35 am

Seg fault for input 4.
Check input and AC output for thousands of problems on uDebug!

uvasarker
Learning poster
Posts: 96
Joined: Tue Jul 19, 2011 12:19 pm
Location: Dhaka, Bangladesh
Contact:

Re: 686 - Goldbach's Conjecture (II)

Post by uvasarker » Thu Feb 09, 2012 7:37 pm

Thanks a lot
Thanks a lot
Thanks a lot
Thanks a lot
Thanks a lot
Finally I got it aaaccc.

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

Re: 686 - Goldbach's Conjecture (II)

Post by brianfry713 » Tue Nov 19, 2013 10:48 pm

Input:

Code: Select all

4
6
10
12
0
AC output:

Code: Select all

1
1
2
1
Check input and AC output for thousands of problems on uDebug!

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

Re: 686 - Goldbach's Conjecture (II)

Post by uDebug » Fri Apr 04, 2014 2:12 pm

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

Input:

Code: Select all

1000
32766
22824
32664
32266
88
23232
0
AC Output:

Code: Select all

28
518
377
498
289
4
428
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

ifti_khar
New poster
Posts: 1
Joined: Wed Apr 23, 2014 4:32 am

Re: 686 - Goldbach's Conjecture (II)

Post by ifti_khar » Wed Apr 23, 2014 4:38 am

WA : 686 - Goldbach's Conjecture (II)
my program give correct ans but judge WA my code is below

#include<bits/stdc++.h>
using namespace std;
int p[32770],ps[3525];
int a,b,c,d,i,j,k,l,m,h,r,q,sr,e;

int main()
{
//freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
for(i=3;i<=32768;i+=2)
p=0;
ps[0]=2;
j=1;
sr=sqrt(32768);
for(i=3;i<=sr;i+=2)
{
if(p==0)
{
ps[j]=i;
j++;
for(k=i*i;k<=32768;k+=i+i)
p[k]=1;
}
}
for(;i<=32768;i+=2)
{
if(p==0)
{
ps[j]=i;
j++;
}
}
a=j-1;
while(cin>>b)
{
if(b==0)
break;
else if(b==4)
cout<<"1\n";
else
{
b=b--;
e=0;
for(r=b;r>=5;r-=2)
{
l=0;
h=a;
for(q=0;q<100;q++)
{
m=(l+h)/2;
if(r==ps[m]||l>h)
break;
else if(r<ps[m])
h=m-1;
else
l=m+1;
}
if(l>h)
continue;
else
break;
}
d=1;
b++;
e=0;
while(1)
{
if(d>m)
break;
if(ps[m]+ps[d]==b)
{
e++;
d++;
}
else if(ps[m]+ps[d]<b)
d++;
else
m--;
}
cout<<e<<"\n";
}

}
return 0;
}

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

Re: 686 - Goldbach's Conjecture (II)

Post by uDebug » Wed Apr 23, 2014 1:20 pm

ifti_khar,

Use code tags to make your code readable. It's tough to debug otherwise.
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

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

Re: 686 - Goldbach's Conjecture (II)

Post by uDebug » Wed Apr 23, 2014 1:31 pm

ifti_khar wrote:my program give correct ans but judge WA my code is below
Change the following line to

Code: Select all

b=b--;
to

Code: Select all

b--;
I did this and submitted your code and got AC.
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

Post Reply

Return to “Volume 6 (600-699)”