1. C, Evgeni Pavlidis


/**
* ACM programming Contest WS 08/09
* UVa Status: accepted
* Run Time: 0.420
* @author Evgeni Pavlidis evgenipavlidis@yahoo.de
*/
#include <stdio.h>
#include <math.h>
#define MAX 100000

int prime[MAX];
int primes = 0;
int maxPrime = 2;

int main()
{
int n;
int c;
while(1)
{
scanf("%d\n", &n);
if(n == 0)
return 0;

for(c=3; c <= n/2; c+=2)
if(checkPrime(c))
if(checkPrime(n-c))
{
printf("%d = %d + %d\n", n , c, n-c);
break;
}

}

}

int checkPrime(int n)
{


int i;
for(i =3; i <= sqrt(n); i++)
if(n % i == 0)
return 0;

return 1;

/**/

/** /
int i;
for(i =0; i < primes; i++)
if(prime[i] == n)
return 1;
return 0;
/**/
}

int isPrime(int n)
{
int c;
for(c = 1; c < primes; c++)
if(n % prime[c] == 0)
return 0;

maxPrime = n;
prime[primes++] = n;

return 1;
}

2. Java, Peter Schnitzler

/* Problem : 495
* Status : AC
* Author : Peter Schnitzler
* Runtime 2.63
*/


import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.math.BigInteger;
import java.util.LinkedList;

import sun.security.util.BigInt;


public class Main
{

static private short max = 0;
static private BufferedWriter outer = new BufferedWriter(new OutputStreamWriter(System.out));

public static void main(String[] args) throws Exception
{
LinkedList<Short> input = getIn();

BigInteger fibbos[] = new BigInteger[max + 1];
fibbos[0] = new BigInteger("0");
fibbos[1] = new BigInteger("1");

for (int count = 2; count <= max; count++)
{
fibbos[count] = fibbos[count - 1].add(fibbos[count - 2]);
}

for (Short i : input)
{
putOut(fibbos[i], i);
}

outer.close();
}




private static void putOut (BigInteger n, short count) throws Exception
{
StringBuilder sB;

sB = new StringBuilder(1335);
sB.append("The Fibonacci number for ");
sB.append(count);
sB.append(" is ");

sB.append(n);



outer.write(sB.toString());
outer.newLine();
}



private static LinkedList<Short> getIn() throws Exception
{
LinkedList<Short> result = new LinkedList<Short>();

BufferedReader read = new BufferedReader(new InputStreamReader(System.in));

String line = read.readLine();

while (line != null)
{
short temp = Short.parseShort(line.trim());

if (temp > max)
max = temp;

result.add(temp);

line = read.readLine();
}

read.close();
return result;
}

}


3. C++, Tobias Fuchs

/* Problem: 543
* Author: Tobias Fuchs
* Verdict: Accepted
* Runtime: 0.630
*/

#include<iostream>
#include<string>

#define log(m) ::std::cout << "log: '" << m << "'" << ::std::endl

using ::std::cin;
using ::std::string;

/* max input value is 1.000.000 = 1000 * 1000
*/
#define MAX_PRIME_SQRT 1000
#define MAX_PRIME (MAX_PRIME_SQRT*MAX_PRIME_SQRT)

/* We want linearized access to this map, so
* do not use ::std::vector, but a simple
* 2-dim array of integers.
*/
bool primes[MAX_PRIME_SQRT][MAX_PRIME_SQRT];

/* Provides serialized accesso to map of primes.
* Map is generated using Sieve of Eratosthenes.
*/
inline bool
is_prime(unsigned int n)
{
return (*primes)[n];
}

/* Building map of primes.
* Implements Sieve of Erastothenes.
*/
void
build_primes()
{
unsigned int step = 2;
unsigned int mark = 1;
memset(primes, true, MAX_PRIME);
while(step < MAX_PRIME_SQRT) {
mark = step;
while(mark+step < MAX_PRIME) {
mark += step;
(*primes)[mark] = false;
}
do { ++step; } while(!is_prime(step));
}
(*primes)[0] = false;
(*primes)[1] = false;
}
void
set_to_next_prime(unsigned int * value_ref) {
do { ++(*value_ref); } while(!is_prime((*value_ref)));
}
void
set_to_prev_prime(unsigned int * value_ref) {
do { --(*value_ref); } while(!is_prime((*value_ref)));
}

int
main()
{
build_primes();

unsigned int sum, a, b, solutions;
string sum_str;
bool done;

while(cin >> sum_str && (sum = atoi(sum_str.c_str())) != 0)
{
a = 2;
b = sum;
done = false;
solutions = 0;
while(!done && a <= b) {
if(a+b < sum) { set_to_next_prime(&a); }
else if(a+b > sum) { set_to_prev_prime(&b); }
if(a+b == sum) {
::std::cout << sum << " = " << a << " + " << b << ::std::endl;
done = true;
}
}
}
return 0;
}