1. C++, Axel Fiedler

/*

* ACM Programming Contest

* Problem: 10394 - Twin Primes

* Status: Accepted

* Language: C++

* Runtime: 0.820

* Date: 2009-03-25 14:16:57

* Author: Axel Fiedler

*/
#include <cstdio>
#include <cmath>

#define highestPrime 20000000
#define maxPrimes 100000

bool isPrime[highestPrime] = {false};
int twinPrimeVec[maxPrimes];

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++)
{
if (isPrime[i])
{
for (int j = i*i; j <= highestPrime; j += i*i)
isPrime[j] = false;
}
}
}

void setTwins()
{
twinPrimeVec[0] = 3;

int pos = 1, p = 0;
for (int i = 6; i <= highestPrime; i += 6)
{
p = i - 1;
if (isPrime[p] && isPrime[p + 2])
{
twinPrimeVec[pos++] = p;

if (pos >= maxPrimes)
break;
}
}
}

int main()
{
sieve();
setTwins();

int n, num;

while ((scanf("%d", &n) == 1) && (n > 0))
{
num = twinPrimeVec[n - 1];
printf("(%d, %d)\n", num, num + 2);
}

return 0;
}