686 - Goldbach's Conjecture (II)

[Tahasin]

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

[A1]

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

[Obaida]

Thanks! Antonio Ocampo I also have a problem like that...
I was thinking about odd primes...
But it should be even & odd both...

[plamplam]

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

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?

[uvasarker]

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]

Seg fault for input 4.

[uvasarker]

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

[brianfry713]

Input:

Code: Select all

4
6
10
12
0

AC output:

Code: Select all

1
1
2
1

[uDebug]

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

[ifti_khar]

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

[uDebug]

ifti_khar,

Use code tags to make your code readable. It's tough to debug otherwise.

[uDebug]

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.