10311 - Goldbach and Euler

[shahriar_manzoor]

Char will not work. Your array is taking 100MB of space anyway which is not allowed. So use one byte to keep info of 8 numbers (one bit for each number). In this way you will need max/8 bytes of space which the judge can allocate.

[trulo17]

[/code]
#include<cstdio>
#include<iostream>
# define max 100000001
# define L 10000
using namespace std;
struct cosa
{
unsigned x : 1;//this is supossed to use one bit
}
A[max];

Code: Select all

why does this get compile error? i'm not sure, but i think this should only use: 100M * bit = 12.5 M but in fact the judge says it's using almost 400M!!!! so i guess the compiler is treating 'x' as an 4 bytes integer when it's supossed to do another thing. any suggestions? thx in advance

[little joey]

The compiler aligns structures on so called memory boundaries. On current day processors memory boundaries occur every 4 bytes (32 bits). Once that was 8 bits (8088 chip), later 16 bits (8086, 80286), but since the 80386 it is 32 bits. Soon it will be 64 bits (Athlon64) or more. So if you have an array of N structures of one bit, it will still occupy 32N bits of memory (or more in the near future).

The best way to implement an array of bits is to define it as an array of some integer type and do some bit manipulation to access the individual bits. You can use (inline) functions or macros to do the bit manipulations. One way to do it is:

Code: Select all

#define MAXBITS 100000000
#define USIZE (8*sizeof(unsigned))

unsigned bitarray[MAXBITS/USIZE];

#define SETBIT(X)    (bitarray[X/USIZE]|=1<<(X%USIZE))
#define RESETBIT(X)  (bitarray[X/USIZE]&=~(1<<(X%USIZE)))
#define GETBIT(X)    ((bitarray[X/USIZE]&(1<<(X%USIZE)))?1:0)

I used an array of unsigned to implement the bitarray. The use of the sizeof() operator doesn't slow down your code (the value of USIZE is resolved at compile time), but makes it portable to other processors and compilers.

[trulo17]

well little joey, i just got acc after your post . I coudn`t managed to work with bits before your post, now it's all very clear. Thanks for replying, that's that kind of help someone always need, bye.

[Nazmul Quader Zinnuree]

Hi,
I'm getting MLE. But don't know how.
Can anybody help me....plz
Here's my C code

Code: Select all

Cut it off

Thanks

[angga888]

#define LIMIT 100000005
#define BLOCK sizeof(char)

char prime[(LIMIT / BLOCK) / 2 + 2];

I think it should be

Code: Select all

#define LIMIT 100000005
#define BLOCK 8*sizeof(char)

char prime[(LIMIT / BLOCK) / 2 + 2];

[Nazmul Quader Zinnuree]

AC now. thanks

[athlon19831]

why?
my code:

#include "stdafx.h"
#include "iostream.h"
#include "math.h"
int main(int argc, char* argv[])
{
int i,j;
int n;
int m,k;
bool flag;
int min;
int m1,k1;
while(cin>>n)
{
flag=false;
m=2;
k=n-m;
min=100000000;
while(m<=k)
{
for(i=2;i<=sqrt(m);i++)
{
if(m%i==0)
i=m;
}
i--;
for(j=2;j<=sqrt(k);j++)
{
if(k%j==0)
j=k;
}
j--;
if(i<sqrt(m)&&j<sqrt(k))
{
if(k-m<min)
{
min=k-m;
m1=m;
k1=k;
}
m++;
k--;
flag=true;
}
else
{
m++;
k--;
}
}
if(flag&&k1>m1)
cout<<n<<" is the sum of "<<m1<<" and "<<k1<<"."<<endl;
else
cout<<n<<" is not the sum of two primes!"<<endl;
}
return 0;
}

[Ashganek]

I guess too many for and while ;P

I made it this way:

1. get primes into array
2. if n lower then 5 - not sum
3. if n is odd
3.1 if n-2 is prime - sum of 2 and n-2
3.2 else not sum
4. if n is even get half of it and serach for first prime bigger and lower then n/2
4.1 if sum of them is n - sum of them
4.2 if sum of them is bigger then n - leave bigger prime and change lower to next lower prime - goto 4.1
4.3 if sum of them is lower then n - leave lower prime and change bigger to next bigger primr - goto 4.1
do this untill this two numbers are between 2 - n-2

[smilitude]

10311 - goldbach and euler - this problem needs to generate a prime sieve upto 100000000 and the thing is even if i use a little optimization like just checking the odd numbers i need to use 50 megs of memory while the memory limit is 40meg.

If i could use bitfields (char 11111111 - 8 bits = 1 byte), i could reduce the memory use by factor of 8 and easily cope with this problem.

I know the basics of bitwise operations, but i dont know how to access a definite bit in C, and how to assign 1 or 0 in that bit field.

I have seen some codes of older programmers and those codes led me to something totally obscure. Can anyone help me? I think this problem might be faced by other younger programmers too. So they will be benefitted as well as me.

Thanking you~!

[mf]

You don't have to sieve up to 100M! Sieve as much as you can, then use your sieve to test primality of smaller numbers and trial division by primes (or Rabin-Miller) for larger ones.

I know the basics of bitwise operations, but i dont know how to access a definite bit in C, and how to assign 1 or 0 in that bit field.

Setting k-th bit of x: x |= 1 << k;
Clearing k-th bit: x &= ~(1 << k);
Getting k-th bit: return (x >> k) & 1;
Flipping k-th bit: x ^= 1 << k; (replaces 0 by 1, and 1 by 0.)
(Here, least significant bit is bit #0.)

[smilitude]

wow~!

thanks a lot mf~!
thanks a lot~!

[smilitude]

O Programmer~!
Show your mercy on me~!
Thou hast made me endless, such is thy pleasure~! (!!)
This frail vessel thou emptiest again and again, and fillest it ever with fresh life~!

Code: Select all

/*
 * 10311 goldbach and eular TLE
 *
 */

#include <stdio.h>
#include <string.h>
#define REMAX 100000000
#define MAX REMAX/16+1


char chkbit[MAX];

bool get(long long x) {
    return (chkbit[x/8]>>(x%8))&1;
}       

//fuction for sieve forming
void generate_sieve() {
	long long num;
	long long temp;
	long long ntemp;
	//memset(chkbit, 0, MAX);
	for(num=3;num<REMAX;num+=2) {
		if(get(num/2)==0) {
			for(temp=num+num;temp<REMAX;temp+=num) {
				if (temp%2) {
                    ntemp=temp/2;
                    chkbit[ntemp/8] |= 1 << (ntemp%8);
                }     
 			}
		}
	}
}

//function for sieve checking
int isprime(long long num) {
	
	if(num==1) return 1;
	if(!get(num/2)) return 1;
	
	return 0;
}



//main function 
int main() {
	long long num,mid,up,down;
	generate_sieve();
	//printf("total memory : %.2lf megabyte\n",(double)sizeof(chkbit)/1000000);
	
	while(scanf("%lld",&num)==1) {
		if(num<3) {
		    printf("%lld is not the sum of two primes!\n",num);
      		continue;
		}if(num%2) {
		    if(isprime(num-2)) 
		        printf("%lld is the sum of 2 and %lld.\n",num,num-2);
      		else printf("%lld is not the sum of two primes!\n",num);
      		continue;
		}else {
		    bool found=false;
		    mid=num/2;
		    if(mid!=2 && mid%2==0) mid--;
		    		    
		    for(;mid>3;mid-=2) {
		        if(isprime(mid) && isprime(num-mid)) {
		            if(mid>(num-mid)) {
		                up=mid;
		                down=num-mid;
		            }else {
		                up=num-mid;
		                down=mid;
		            } 
                    printf("%lld is the sum of %lld and %lld.\n",num,down,up);
                    found=true;
                    break;
                }
            }
            if(found==false) printf("%lld is not the sum of two primes!\n",num);
        }
    }
return 0;
}            
         

( sorry to a nobel winner poet! )

[Moha]

One hint, you can change a/8 into a>>3 and a%8 into a&7 try it!
Another thing is if you declare get function as define, you would speed up your code.
My code is very similar to yours.

[smilitude]

Your idea is really g-r-e-a-t !
A good friend of mine, sunny, showed me something different -->

here's the sieve part of my code

Code: Select all

for(num=3;num<REMAX;num+=2) {
        if(get(num/2)==0) {
            for(temp=num+num;temp<REMAX;temp+=num) {
                if (temp%2) {
                    ntemp=temp/2;
                    chkbit[ntemp/8] |= 1 << (ntemp%8);
                }    
             }
        }
}

it is better when its written as -->

Code: Select all

limit = (long long) sqrt(REMAX);
for(num=3;num<=limit;num+=2) {
	if(get(num/2)==0) {
		for(temp=num*num;temp<REMAX;temp+=2*num) {
		    if (temp%2) {
                    ntemp=temp/2;
                    chkbit[ntemp>>3] |= 1 << (ntemp&7);
                }     
 	    }
	}
}

changing the inner two loops and preventing checking like 3, 6, 9, 12, ...

and thus with the generous help of you guys i finally edited the code into this, editing some more err... -->

Code: Select all

/*
 * 10311 goldbach and eular TLE
 *
 */

#include <stdio.h>
#include <string.h>
#define REMAX 100000000
#define MAX REMAX/16+1
#define get(x) ((chkbit[x>>3]>>(x&7))&1)
#define isprime(x) (!get(num/2))

char chkbit[MAX];


//fuction for sieve forming
void generate_sieve() {
	long long num;
	long long temp;
	long long ntemp;
	long long limit;
	limit = (long long) sqrt(REMAX);
	//memset(chkbit, 0, MAX);
	for(num=3;num<limit;num+=2) {
		if(get(num/2)==0) {
			for(temp=num*num;temp<REMAX;temp+=2*num) {
				if (temp%2) {
                    ntemp=temp/2;
                    chkbit[ntemp>>3] |= 1 << (ntemp&7);
                }     
 			}
		}
	}
}

//main function 
int main() {
	long long num,mid,up,down;
	generate_sieve();
	//printf("total memory : %.2lf megabyte\n",(double)sizeof(chkbit)/1000000);
	
	while(scanf("%lld",&num)==1) {
		if(num<3) {
		    printf("%lld is not the sum of two primes!\n",num);
      		continue;
		}if(num%2) {
			if(isprime(num-2)) {
				if((num-2)>2) 
					printf("%lld is the sum of 2 and %lld.\n",num,num-2);
				else printf("%lld is the sum of %lld and 2.\n",num, num-2);
			}else printf("%lld is not the sum of two primes!\n",num);
      		continue;
		}else {
		    bool found=false;
		    mid=num/2;
		    if(mid!=2 && mid%2==0) mid--;
		    
		    for(;mid>0;mid-=2) {
		        if(isprime(mid) && isprime(num-mid)) {
		            if(mid>(num-mid)) {
		                up=mid;
		                down=num-mid;
		            }else {
		                up=num-mid;
		                down=mid;
		            } 
                    printf("%lld is the sum of %lld and %lld.\n",num,down,up);
                    found=true;
                    break;
                }
            }
            if(found==false) printf("%lld is not the sum of two primes!\n",num);
        }
    }
return 0;
}            
         

and again Thou hast made me endless, such is thy pleasure~! (!!) has occured, why am i getting TLE now??