1. 

package acm_10311_goldbach_and_euler;

import java.util.Scanner;

/**
* FWP, Ausgew¦hlte Probleme aus dem ACM Programming Contest, SS10
* Problem: acm_10311_goldbach_and_euler
* Link:
*
* @author Martin Lambeck
* @version 1.0, 14.09.2010
*
* Method : sieve, bitfield
* Status : Accepted
* Runtime: 5.826
*/


public class Main
{
static final int intbits = 32;
static final int MAX = 100000000;
static int[] composed = new int[MAX/intbits + 1]; //bitfield 0 = prime, 1 = composed (wrong values for 0 and 1)
static Scanner sc = new Scanner(System.in);

public static void main(String... args)
{
init();

while (sc.hasNextInt())
testcase();
}

public static void init()
{
int sqrtMax = (int)Math.sqrt(MAX);
int ind;
int ofs;
int cp;

for (int i = 2; i <= sqrtMax; i++)
{
ind = i / intbits;
ofs = i % intbits;
cp = (composed[ind] >> ofs) & 1;

if (cp == 0) //if i is prime
{
for (int j = i*i; j <= MAX; j += i) //all multiples of i are composed
{
ind = j / intbits;
ofs = j % intbits;
composed[ind] |= 1 << ofs; //j is composed
}
}
}
}

public static void testcase()
{
int n = sc.nextInt();

int ind, ofs, cp;


if ((n <= 4) || (n == 6)) //special cases
{
System.out.printf("%d is not the sum of two primes!%n", n);

} else if ((n & 1) > 0) //n is odd. if (n-2) is prime then n is the sum of n-2 and 2
{
ind = (n-2) / intbits;
ofs = (n-2) % intbits;
cp = (composed[ind] >> ofs) & 1;

if (cp == 0)
{
System.out.printf("%d is the sum of 2 and %d.%n", n, n-2);
} else
{
System.out.printf("%d is not the sum of two primes!%n", n);
}

} else
{
int bottom = n / 2 - 1; //bottom+top = n, bottom < top
int top = n / 2 + 1; //first possible pair of values (highest bottom, lowest top)

while (true) //there always is a solution (otherwise we would have rejected goldbach conjecture ;) )
{
ind = top / intbits;
ofs = top % intbits;
cp = (composed[ind] >> ofs) & 1;

if (cp == 0) //top is a prime
{
ind = bottom / intbits;
ofs = bottom % intbits;
cp = (composed[ind] >> ofs) & 1;

if (cp == 0) //bottom is a prime, too
{
System.out.printf("%d is the sum of %d and %d.%n", n, bottom, top);
break;
}
}

top++; //try next pair
bottom--;
}
}
}
}