10311 - Goldbach and Euler

[Moha]

you can alse speed it up with this code:

Code: Select all

for(num=5,f=2;num<REMAX;num+=f,f=6-f)

You should handle 3 separatly. It is faster than yours by 33%.

[smilitude]

After skipping TLE and getting 5 consecutive WA, this frail vessel being emptiest again and again, is fillest ever with fresh life~!

I got accepted!

Thanks a looooooot moha! thanks a loooooooooooooot!

[Pasa Yildirim]

Hi all!

Well, I was searching around for sieve optimisation, and i was found it here:
http://online-judge.uva.es/board/viewto ... ight=#6457

I implemet this, but I got TLE (> 30sec). It works perfect at me.

Here is the code:

Code: Select all

#include <cstdio>
using namespace std;

#define MAX	100000000
#define HALF	50000000
#define SQRT	5000
#define SIZE	MAX / 16 + 2

char SITO[SIZE];

#define NTH(n)           ((n) & 7)
#define ISPRIME(n)    SITO[n >> 4] & (1 << NTH (n >> 1))

bool isprime (int n)
{
	if (n == 2) return true;
	else if (!(n & 1)) return false;
	else return ISPRIME (n);
}

void init (void) 
{
	memset (SITO, 0xff, sizeof SITO);		
	SITO[0] = 0xFE;
	for (int i = 1; i < SQRT; i++)
		if (SITO[i >> 3] & (1 << NTH (i)))
			for (int j = 2 * i * (i + 1); j < HALF; j += 2 * i + 1)
				SITO[j >> 3] &= ~(1 << NTH (j));
}

/*** CUTTED ***/

Thank you in advance!

PY

[mf]

Your program takes more than a second to find answer to 99999999 (after preprocessing).
You have to solve such tests (when n is odd) much faster.

Also, your program can produce wrong answers -- read the last paragraph of the "Output" section of the problem statement.

[Pasa Yildirim]

Hello, mf!
Thank you for the reply. I fixed my main function, but it's still TLE.
I tested big integers now, it's secondary fast.

Code: Select all

/*** CUTTED ***/

Any ideas?

[mamun]

Code: Select all

if (!(n & 2))

What is this line supposed to do?

[Pasa Yildirim]

Thank you, mamun. I fix that, but it is still TLE.

I tested it on input 99999999, it gets immediatly the result.
Sieving takes about 3-4 secs at me (2.8GHz).

Can sieve be faster?

Regards,
PY

[mamun]

Seive may be faster but that is not the major problem here. Post your modified code. You'll get enough informartion if you search the forum for this problem.

[Pasa Yildirim]

My modified code:

Code: Select all

/*** CUTTED ***/

[mamun]

Try with an even number say 100000000. Since your machine is very fast, so you may not understand the delay unless you give a lot of inputs of such.

You must understand that if an odd number is to be sum of two primes then one of them has to be 2, otherwise not. So avoid calculation involving odd numbers.

Code: Select all

for (int i = n / 2 - 1; i >= 0; i -= 2)

i can be even here for some even n and continues to be even.

[Pasa Yildirim]

Thank you for reply!

If I understood You, Mamun, here

Code: Select all

      if (n % 2 == 1 && isprime (n - 2))
      {
         printf ("%d is the sum of %d and %d.\n", n, 2, n - 2);
         goto end;
      } 

I check wheter is number is odd, and if it is odd hen I do what You said.

i can be odd here for some even n and continues to be odd.

I assumed it must be odd because the even number must be of two odd numbers. Now I'm a little bit confused. I can't remember other way for finding is the number sum of two primes.

[mamun]

Sorry, I was little wrong, I've corrected my previous post's last line.

What I actually wanted to mean is

Code: Select all

for (int i = n / 2 - 1; i >= 0; i -= 2)

value of i can be even for even n like 99999998 and continues to be even. So your loop runs to the end and consumes time.

You'll get wrong answer too.

Code: Select all

if (n % 2 == 1 && isprime (n - 2)) 
{ 
   printf ("%d is the sum of %d and %d.\n", n, 2, n - 2); 
   goto end; 
}

What if n is odd and (n-2) is not prime?

[Pasa Yildirim]

Mamun, thank You very much. I finnaly got AC (about 7.8 sec). :D

The problem was in 9999998. Anybody who stuck in TLE and has got fast sieve should try this input.

Thank you again!

[serur]

Hi fellows!

I need to hold a variable balance in my balanced search trees, but to make it int or even signed char would be no good - I read in my book that I can make it "bit field with sign".
Please, tell me how to do it.
I know now (thanks mf ) how to make that kind of thing with arrays (for Seat of Eratosphean ), but whaT is "signed bit field"?

Thank you.

[serur]

Hi everyone!

My definition of bitfield:

Code: Select all

typedef struct{
	signed char s:1;
}bit_field;

int main(){
	bit_field  sign;
	return 0;
}

How to assign to sign variable 0 and 1?