1. C++, Axel Fiedler


/*

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

2.

/*

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