1.

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS09
* Problem: 10311 Goldbach and Euler
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=15&page=show_problem&problem=1252
*
* @author Christoph Hausmann
* @version 0.1, 10/21/2009
*
* Method : Sieve of Eratosthenes for prime generation.
* Status : Accepted
* Runtime: 6.160
*/

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;


public class GoldbachAndEuler_10311 {
public static void main(String... args) throws NumberFormatException, IOException {
final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

final boolean[] noPrimes = computePrimes(100000001); // tells whether number at index i is not a prime (true), or is a prime (false)

while(true) {
final String curLine = br.readLine();
if(curLine == null)
break;

final int curNum = Integer.parseInt(curLine);

boolean isSum = false; // is this a sum of two primes?
int num1 = -1; // smaller prime
int num2 = -1; // bigger prime

if(curNum > 4) {
if(curNum%2 == 0) {
for(int i = (curNum/2); i > 2; i--) {
if(!noPrimes[curNum-i] && !noPrimes[i]) {
num2 = curNum-i;
num1 = i;

if(num2-num1 <= 0)
continue;
else {
isSum = true;
break;
}
}
}
} else {
if(!noPrimes[curNum-2]) {
num1 = 2;
num2 = curNum-2;
isSum = true;
}
}
}

if(isSum) {
System.out.print(curNum + " is the sum of " + num1 + " and " + num2 + ".\n");

} else {
System.out.print(curNum + " is not the sum of two primes!\n");
}
}
}


private static boolean[] computePrimes(int n) {

final boolean[] noPrimes = new boolean[n];

Arrays.fill(noPrimes, false);

for(int i = 2; i*i <= n; i++) {
if(!noPrimes[i]) {
for(int j = i*i; j < n; j+=i) {
noPrimes[j] = true;
}
}
}

return noPrimes;
}
}