10311 - Goldbach and Euler

[smilitude]

hi serur,
once i waste a lot of time working bit field in this way... but i couldnt make it working... then for a while i used to remember the way mf described about changing value... then when i read the bit field things well in a language book, i became clear.
if you dont mind, in my humble opinion, it would be much wiser to read the basic works of bit field, then look at what mf tried to tell. Then go ahead and work on simple bit fields...

you can also have a look here ... http://online-judge.uva.es/board/viewtopic.php?t=10418

i dont know well about balanced search trees, but i think 'bit field with sign', here sign means for flagging... not anything other... and chars are signed by default...

[mamun]

Code: Select all

struct{ 
   signed char s:1; 
}bit_field;

Don't you think here bit_field takes just 1 bit of memory but the whole word which maybe 4 bytes. Assigning value to this bit_field is just like struct structures.

Code: Select all

bit_field  sign;
sign.s=1;

But I'm sure you want memory efficiency. Try to understand what mf has written. Read more about low level programming to clear yourself.

[serur]

Hi fellows!

Thank you smilitude and mamun for sympathy

mamun wrote:

But I'm sure you want memory efficiency

Yes, all I want is memory efficiency

but:

mamun wrote:

Don't you think here bit_field takes just 1 bit of memory but the whole word which maybe 4 bytes

Yes, you are right, and I WANT ONLY 1 BIT MEMORY FOR SIGN AND NO MORE!
Also, I'd like to use int as base instead of char.

Well, UNIX is only 10% assembly and 90% in C! So I'll work hard to understand these low-level stuffs. But a tiny hint is welcome, all the same

[898989]

please i got many wa.......
This is my even part is it wrong

Code: Select all

		if(n % 2 == 0)	//So even //Test all possiblities eficiently
		{
			bool flag = false;
			int mid = n / 2;	//Any number is divided to 2 sides 
			
			if(mid != 2 && mid % 2 == 0) 
				--mid;	//Start from odd and use -=2 Optimization
			
			for(int k = mid; k > 0; k -= 2)//(p2-p1) is positive and minimized
			{
				if(isprime(k) && isprime(n - k))
				{
			//		if(k < n-k)
						possible(n, k, n - k);
			//		else
			//			possible(n, n - k, k);
					flag = true;
					break;
				}
			}
			if(!flag) 
				cout<<n<<" is not the sum of two primes!"<<"\n";
}

Please i need some test cases
also what is the output for

Code: Select all

1
2
3
4
5
6
7
8
9
10
11
12

[Darko]

In my solution I would check if mid is even, and if yes do mid--, if not mid-=2. (without that mid != 2 part)
And my loop would go down to 3 (not to 1).

For that input:

Code: Select all

1 is not the sum of two primes!
2 is not the sum of two primes!
3 is not the sum of two primes!
4 is not the sum of two primes!
5 is the sum of 2 and 3.
6 is not the sum of two primes!
7 is the sum of 2 and 5.
8 is the sum of 3 and 5.
9 is the sum of 2 and 7.
10 is the sum of 3 and 7.
11 is not the sum of two primes!
12 is the sum of 5 and 7.

[898989]

THANKS THANKS THANKS THANKS THANKS THANKS
THANKS THANKS THANKS THANKS THANKS THANKS

I got accepted NOWWWWWWWW FINALYYY

http://acm.uva.es/problemset/usersjudge.php?user=8957

[kolpobilashi]

plz tell wht this code's giving me MLE???

Code: Select all

cut

thanx in advance..

[ayon]

isn't it very simple? ur prim[] array is taking more than 47MB, where the judge memory limit is 32MB

[kolpobilashi]

yes i understood the problem...but the thing is what should i do then.??
if i don't generate the primes before.....and each time check... that will certainly give TLE.
plz suggest me..

[sunny]

yes i understood the problem...but the thing is what should i do then.??
if i don't generate the primes before.....and each time check... that will certainly give TLE.
plz suggest me..

use bits. here is a sample if u want 2 access the X'th bit of a char array.

Code: Select all

#define MAX 100000000 
char  flag[MAX/8]; 
#define SETBIT(X) (flag[X/8]|=1<<(X%8)) 
#define GETBIT(X) ((flag[X/8]&(1<<(X%8)))?1:0) 

[ayon]

if you know bitwise operation in C, it will be rather easy using char array as sunny said. better process is using char array of size[MAX/16]. it deals with only odd numbers, as you know even numbers are not prime(except 2). 1st character of the char array represents whether 1, 3, 5, 7, 9, 11, 13, 15 are prime or not, 2nd character represents 17,19,...,31, etc. you can have a look at http://www.shygypsy.com/tools/number.cpp to get the C code

[kolpobilashi]

thanx sunny & ayon...this bitwise operation seems much complicated but it really works

[<:3)~~]

I am using Miller's Primality test even then its TLE!!! And when i used sieve its MLE!! I read previous posts but i cant understand how they r managing not to MLE!! some one plzz help!

[<:3)~~]

why isnt any one replying!!!!!!

[Jan]

Dont open a new thread unless there is none. First search your problem. And when creating a new thread try to write the subject like '10311 - Goldbach and Euler'.

Remember that you can use bitwise sieve.