Prime Numbers

Sieve of Eratosthenes: 

#include <cmath>
const int MAX = 1000000;
const int SQRT_MAX = (int)sqrt(MAX);

short primes[MAX];
void gen_primes() 
{ 
  for(int i=0;i<MAX;i++) 
    primes[i] = 1; 
  for(int i=2; i<= SQRT_MAX;i++) 
    if (primes[i]) 
      for(int j=i;j*i<MAX;j++) 
        primes[i*j] = 0; 
} 

or use our bitvector to store primes[]:

Problem: UVa 543: Goldbach's Conjecture

#include <iostream>
const int MAX = 1000001;
const int SQRT_MAX = 1000;

const int SHIFT = 5;
const int MASK = (1<<SHIFT)-1;

inline void SET(unsigned int a[], int i) {
	a[i>>SHIFT] |= (1 << (i & MASK));
}
inline void CLEAR(unsigned int a[], int i) {
	a[i>>SHIFT] &= ~(1 << (i & MASK));
}
inline bool TEST(unsigned int a[], int i) {
	return a[i>> SHIFT] & (1 << (i & MASK));
}

const unsigned int N = MAX/(sizeof(int)<<3);
unsigned int primes[N+1];

void gen_primes() 
{ 
    memset(primes, 0xAAAAAAAA, sizeof(primes));
    SET(primes, 2);
    for(int i = 3; i <= SQRT_MAX; ++ i) {
        if (TEST(primes, i))  {
            for(int j = i; j * i < MAX; ++ j)  {
                CLEAR(primes, i * j);
            }
        }
    }
} 

int main() {
    gen_primes();
    int n;
    while(scanf("%d ", &n) && n) {
        unsigned int i = 2, pos = 0;
        while(true) {
            unsigned int p = n-i;
            if(TEST(primes,i) && TEST(primes, p)) {             
                printf("%d = %d + %d\n", n, i, p);
                break;
            }
            while(!TEST(primes,++i)) {};
        }
    }
}