1.

/**
* ACM
* UVa Status: accepted
* Run Time: 7.000
* Category: Math
* @author Evgeni Pavlidis evgenipavlidis@yahoo.de
*/
import java.io.*;
import java.util.*;
import java.math.*;


public class Main {

/**/
// implementation and memory consumption of BitSet in java is way too slow
// and we need a bit set because an array of bools needs too much memory
private static class BitSet {

private int[] set;
private int size;

BitSet(int size)
{
this.size = size;
set = new int[size/32+1];
}

public void set(int startIndex, int endIndex)
{
for(int i=0; i <= size/32; i++)
set[i] = 0xFFFFFFFF;
set(1, false);
}
public void set(int pos, boolean value)
{
if(value)
set[pos>>5] |= (1<<(pos & 0x0000001F));
else
set[pos>>5] &= ~(1<<(pos & 0x0000001F));
}

public void set(int pos)
{ this.set(pos, true); }

public boolean get(int pos)
{ return (set[pos>>5] & (1<<(pos & 0x0000001F))) != 0; }
}

/**/

public static int MAX_N = 100000000;
public static int MAX_PRIME = 100000000;

//private static boolean[] isPrime= new boolean[MAX_PRIME+1];
private static BitSet isPrime = new BitSet(MAX_PRIME);
private static int n;

static void generatePrimes()
{
isPrime.set(2,MAX_PRIME);

int squareRoot = (int)Math.sqrt(MAX_PRIME);
for(int i=2; i <= squareRoot; i++)
if(isPrime.get(i))
for(int j=i+i; j <= MAX_PRIME; j+=i)
isPrime.set(j,false);
}

public static void main(String...args) throws Exception
{
int firstPrime;
generatePrimes();

BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

String input;

while((input = reader.readLine()) != null && !input.equals(""))
{
n = Integer.parseInt(input);
firstPrime = -1;

if(n % 2 == 1)
{
if(n!=1 && isPrime.get(n-2))
firstPrime = 2;
}
else
for(int i=n/2; i >= 2; i--)
if(isPrime.get(i) && (n-i != i) && isPrime.get(n-i))
{
firstPrime = i;
break;
}

if(firstPrime == -1)
out.printf("%d is not the sum of two primes!\n",n);
else
out.printf("%d is the sum of %d and %d.\n",n,firstPrime,n-firstPrime);
}
out.flush();
}
}


2.

/**
* ACM
* UVa Status: accepted
* Run Time: 6.460
* Category: Math
* @author Evgeni Pavlidis evgenipavlidis@yahoo.de
*/
#include <iostream>
#include <cmath>

using namespace std;

#define MAX_N 100000000
#define MAX_PRIME 100000000

static bool isPrime[MAX_PRIME];
static int n;

void generatePrimes()
{
for(int i=2; i <= MAX_PRIME; i++)
isPrime[i] = 1;

int squareRoot = (int)sqrt(MAX_PRIME);
for(int i=2; i <= squareRoot; i++)
if(isPrime[i] == 1)
for(int j=i+i; j <= MAX_PRIME; j+=i)
isPrime[j] = 0;
}


int main()
{
bool found;
int firstPrime;
generatePrimes();

while(cin >> n)
{
firstPrime = -1;

if(n % 2 == 1)
{
if(isPrime[n-2])
firstPrime = 2;
}
else
for(int i=n/2; i >= 2; i--)
if(isPrime[i] && (n-i != i) && isPrime[n-i])
{
firstPrime = i;
break;
}

if(firstPrime == -1)
printf("%d is not the sum of two primes!\n",n);
else
printf("%d is the sum of %d and %d.\n",n,firstPrime,n-firstPrime);

}
return 0;
}

3.

/*

* ACM Programming Contest

* Problem: 10311 - Goldbach and Euler

* Status: Accepted

* Language: C++

* Runtime: 5.650

* Date: 2009-03-25 14:16:57

* Author: Axel Fiedler

*/
#include <iostream>
#include <cmath>

#define highestPrime 100000000

bool isPrime[highestPrime] = {false};

void sieve()
{
isPrime[2] = true;
isPrime[3] = true;

int n, iQuad, jQuad, limit = sqrt((long double)highestPrime);

for (int i = 1; i <= limit; i++)
{
iQuad = i*i;
for (int j = 1; j <= limit; j++)
{
jQuad = j*j;

n = (iQuad << 2) + (jQuad);
if ((n <= highestPrime) && ((n%12 == 1) || (n%12 == 5)))
isPrime[n] = !isPrime[n];

n = 3*(iQuad) + (jQuad);
if ((n <= highestPrime) && (n%12 == 7))
isPrime[n] = !isPrime[n];

n = 3*(iQuad) - (jQuad);
if ((i > j) && (n <= highestPrime) && (n%12 == 11))
isPrime[n] = !isPrime[n];
}
}

for (int i = 5; i <= limit; i += 2)
{
if (isPrime[i])
{
iQuad = i*i;
for (int j = iQuad; j <= highestPrime; j += iQuad)
isPrime[j] = false;
}
}
}

int main()
{
int n;

sieve();

while (std::cin >> n)
{
if (n < 5)
{
std::cout << n << " is not the sum of two primes!" << std::endl;
}
else if (n == 6)
{
std::cout << "6 is not the sum of two primes!" << std::endl;
}
else if (n & 1)
{
if(isPrime[n - 2])
std::cout << n << " is the sum of 2 and " << n - 2 << "." << std::endl;
else
std::cout << n << " is not the sum of two primes!" << std::endl;
}
else
{
for (int i = ((n/2) & 1) ? (n/2) : (n/2) - 1; i >= 2; i -= 2)
{
if (isPrime[i] && isPrime[n - i] && (n - i != i))
{
std::cout << n << " is the sum of " << i << " and " << n - i << "." << std::endl;
break;
}
}
}
}

return 0;
}

4.

/*

* ACM Programming Contest

* Problem: 10311 - Goldbach and Euler

* Status: Accepted

* Language: C

* Runtime: 2.204

* Date: 2009-05-12 19:04:59

* Author: Axel Fiedler

hier noch eine neue Version von Goldbach und Euler. Diesmal mit Bit-Set
anstatt einem Bool-Array, was schon doppelt so schnell ist.


*/
#include <math.h>
#include <stdio.h>

#define highestPrime 100000000

int primes[highestPrime/32 + 1];

#define setPrime(x) (primes[x>>5] |= (1<<(x & 0x0000001F)))
#define unsetPrime(x) (primes[x>>5] &= ~(1<<(x & 0x0000001F)))
#define setAndNegatePrime(x) ((primes[x>>5] & (1<<(x & 0x0000001F))) ? (primes[x>>5] &= ~(1<<(x & 0x0000001F))) : (primes[x>>5] |= (1<<(x & 0x0000001F))))
#define isPrime(x) (primes[x>>5] & (1<<(x & 0x0000001F)))

void sieve()
{
int i, j, n, iQuad, jQuad, limit = sqrt((long double)highestPrime);

setPrime(2);
setPrime(3);

for (i = 1; i <= limit; i++)
{
iQuad = i*i;
for (j = 1; j <= limit; j++)
{
jQuad = j*j;

n = (iQuad << 2) + (jQuad);
if ((n <= highestPrime) && ((n%12 == 1) || (n%12 == 5)))
setAndNegatePrime(n);

n = 3*(iQuad) + (jQuad);
if ((n <= highestPrime) && (n%12 == 7))
setAndNegatePrime(n);

n = 3*(iQuad) - (jQuad);
if ((i > j) && (n <= highestPrime) && (n%12 == 11))
setAndNegatePrime(n);
}
}

for (i = 5; i <= limit; i += 2)
{
if (isPrime(i))
{
iQuad = i*i;
for (j = iQuad; j <= highestPrime; j += iQuad)
unsetPrime(j);
}
}
}

int main()
{
int n, i;

sieve();

while ((scanf("%d", &n) > 0) && (n > 0))
{
if (n < 5)
{
printf("%d is not the sum of two primes!\n", n);
}
else if (n == 6)
{
printf("6 is not the sum of two primes!\n", n);
}
else if (n & 1)
{
if(isPrime(n - 2))
printf("%d is the sum of 2 and %d.\n", n, n - 2);
else
printf("%d is not the sum of two primes!\n", n);
}
else
{
for (i = ((n/2) & 1) ? (n/2) : (n/2) - 1; i >= 2; i -= 2)
{
if (isPrime(i) && isPrime(n - i) && (n - i != i))
{
printf("%d is the sum of %d and %d.\n", n, i, n - i);
break;
}
}
}
}

return 0;
}