1.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.BitSet;
/**
* Angewandte Mathematik, SS11
* 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 Benedikt Z¨nnchen
* @author Erik Wenzel
* @version 1.0, 04/02/2011
*
* Method : Sieb, Alle ungeraden m¾ssen mit 2+x gebildet werden k¨nnen
* Status : Accepted
* Runtime: 3.832
*/

public class Main
{
public static void main(String[] args)
{
//long time = System.currentTimeMillis();
BufferedReader sc;
BitSet noPrimes = calcNoPrimesSet(100000000);
try
{
sc = new BufferedReader(new InputStreamReader(System.in));

int number;
boolean prime;
int a = 0;
int b = 0;
String line;

while((line = sc.readLine())!=null)
{
number = Integer.parseInt(line);
prime = false;
if(number>=5)
{
// number ist ungerade
if(number%2 != 0)
{
if(!noPrimes.get(number-2))
{
b = number-2;
a = 2;
prime = true;
}
else
{
prime = false;
}
}
// number ist gerade
else
{
//System.out.println("test");
int j = (number/2);
if(j%2 == 0)
{
j--;
}
for(int i=j; i > 0; i-=2)
{
//System.out.println(i);
b = number-i;
a = i;

if(a!=b && !noPrimes.get(a) && !noPrimes.get(b))
{
prime = true;
break;
}
}
}
}

// Ausgabe
if(!prime)
{
System.out.println(number + " is not the sum of two primes!");
}
else
{
System.out.println(number + " is the sum of " + a + " and " + b + ".");
}
}
//System.out.println(System.currentTimeMillis()-time);
sc.close();
}
catch (Exception e)
{
e.printStackTrace();
}

}

/**
* Errechnet alle Zahlen die keine Primzahlen sind. Somit ist klar,
* dass alle Zahlen die nicht in der Menge sind Primzahlen sind.
* Das System geht nach dem Sieb des Eratosthenes. Alle Vielfachen einer
* Zahl sind automatisch keine Primzahl!
* @param maxPrime Obergrenze
*/
public static BitSet calcNoPrimesSet(int maxPrime)
{
BitSet set = new BitSet();
set.set(0);
set.set(1);
for (int i = 2; i <= Math.sqrt(maxPrime); ++i)
{
if (!set.get(i))
{
for (int j = i * i; j <= maxPrime; j += i)
{
set.set(j);
}
}
}
return set;
}

/**
* Errechnet alle Zahlen die keine Primzahlen sind. Somit ist klar,
* dass alle Zahlen die nicht in der Menge sind Primzahlen sind.
* Das System geht nach dem Sieb des Eratosthenes. Alle Vielfachen einer
* Zahl sind automatisch keine Primzahl!
* @param maxPrime Obergrenze
*/
public static boolean[] calcNoPrimesArray(int maxPrime)
{
boolean[] noPrimes = new boolean[maxPrime+1];
noPrimes[0] = true;
noPrimes[1] = true;
for (int i = 2; i <= Math.sqrt(maxPrime); ++i)
{
if (!noPrimes[i])
{
for (int j = i * i; j <= maxPrime; j += i)
{
noPrimes[j] = true;
}
}
}
return noPrimes;
}
}



-----------------------------------------------------------------------------------------------

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--;
}
}
}
}