Page 6 of 8

543 - WA "Goldbach's"

Posted: Tue Mar 06, 2012 5:42 pm
by felipej
i can't see where i'm getting wa... can any 1 help?

code:

Code: Select all

GOT AC
thanks...

Re: 543 - WA "Goldbach's"

Posted: Tue Mar 06, 2012 10:33 pm
by brianfry713
14372=3+14369

Re: 543 - WA "Goldbach's"

Posted: Wed Mar 07, 2012 6:27 am
by felipej
thanks a lot! found bug and got AC!

543 why TLE?help plz

Posted: Sun Jul 22, 2012 1:46 pm
by Honour_00
here is my code

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
long long pr[1000080],T;
bool isp[1000080];
void prime()
{
long long i,j;
T=0;
for(i=2;i<1000000;i++)
{
if(isp==0)
{
for(j=i*i;j<1000000;j=j+i)
{
isp[j]=1;
}
pr[T]=i;
T++;
}
}
}
int main()
{
prime();
long long a,s,d,f,g,h,k,l;
while(scanf("%lld",&a)==1)
{
if(a==0) break;
else
{
s=1;
for(d=T-1;d>=0;d--)
{
if(pr[d]>=a) continue;
for(f=0;f<d;f++)
{
if(a==pr[d]+pr[f])
{
s=0;
printf("%lld = %lld + %lld\n",a,pr[f],pr[d]);
break;
}
}
if(s==0) break;
}
if(s==1)
{
printf("Goldbach's conjecture is wrong.\n");
}
}
}
return 0;
}

plz help :(

Re: 543 why TLE?help plz

Posted: Tue Jul 24, 2012 12:45 am
by brianfry713
Your code is too slow. Try stopping the inner loop when pr[d]+pr[f]>a

Re: 543-goldbach's conjecture..RE??

Posted: Wed Aug 15, 2012 3:26 pm
by goldenbird299
hi everyone
can you help me with this code?
it gets RE from judge >_<

Code: Select all

Removed after AC

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

Posted: Wed Aug 15, 2012 9:46 pm
by brianfry713
Try 999998

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

Posted: Thu Aug 16, 2012 6:43 am
by goldenbird299
OMG!
what a mistake!
i thought n < 100000 !!
Thanks Brian :)

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

Posted: Mon Jan 07, 2013 12:27 pm
by gr81
getting WA, please have a look at my code...at http://ideone.com/dR8w5y

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

Posted: Mon Jan 07, 2013 6:04 pm
by gr81
got AC, i forgot if ( n < 4 )...would not get processed...

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

Posted: Tue Jan 08, 2013 10:15 am
by kier.guevara

Code: Select all

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

void primeNumbers(vector <int> &prime, int n)
{
  short array[1000000] = {0};
  
  for(int i = 2; i <= sqrt(n); i++)
  {
    if(array[i] == 0)
    {
     for(int k = i+1; k < n; k++)
     {
       if(k % i == 0)
         array[k] = 1;
     }
    }
  }

  for(int i = 3; i < n; i++)
  {
    if(array[i] == 0)
      prime.push_back(i);
  }
}

void gold(vector <int> &prime, int n)
{
	
	for(int i = prime.size() - 1; i >= prime.size()/2; i--)
	{
		for(int k = 0; k <= prime.size()/2; k++)
		{
		  if(prime[i] + prime[k] == n)
		  {
		   cout << n << " = " <<  prime[k] << " + " << prime[i] << endl;
		   return;   
		  }
		  if(prime[i] + prime[k] > n)
			  break;
		}
	}
	cout << "Goldbach's conjecture is wrong." << endl;
}


int main()
{
  vector <int> prime;
  int n;
  
  while(cin >> n)
  {
    if(n == 0)
      break;

    primeNumbers(prime, n);
    gold(prime,n);
	
  }
 
  return 0;
}
Im getting TLE. Is there any way I can make my code efficient?

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

Posted: Tue Jan 08, 2013 9:27 pm
by brianfry713
http://www.algorithmist.com/index.php/UVa_543
First use the Sieve of Eratosthenes or hard code a list of primes.
Don't regenerate a list of primes for every input. Also make that prime list global.

543 - WA

Posted: Sun Jan 13, 2013 3:00 pm
by hansyulian
What is wrong with my code?

Code: Select all

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;

bool prima[1000005];

int main()
{
	memset(prima,true,sizeof(prima));
	prima[0] = false;
	prima[1] = false;
	for (long i = 2; i < 1000000; i++)
		if (prima[i])
		{
			long j = 2*i;
			while (j < 1000000)
			{
				prima[j] = false;
				j+=i;	
			}	
		}
	long n;
	scanf("%ld",&n);
	while (n)
	{
		long i = 2;
		bool ada = false;
		while (!ada && i < n/2)
		{
			if (prima[i] && prima[n-i])
			{
				ada = true;
				printf("%ld = %ld + %ld\n",n,i,n-i);
			}	
			i++;
		}
		if ( !ada) printf("Goldbach's conjecture is wrong.\n");
		scanf("%ld",&n);	
	}
	return 0;
}

Re: 543 - WA

Posted: Sun Jan 13, 2013 8:38 pm
by brianfry713
6 = 3 + 3

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

Posted: Tue Oct 29, 2013 10:11 pm
by Yusif
I'm getting TL but I cant get why :(

Code: Select all

AC