恩，使用GNU的高精度库写了一个，答案一样……

要编译的话，必须包含libgmp，在Ubuntu下可以：
sudo apt-get install libgmp3-dev
来获得gmp库，编译的时候加上-lgmp参数。

#include <stdio.h>
#include <gmp.h>
#include <stdlib.h>

mpz_t m;

void dfs(mpz_t n, mpz_t deep)
{
    int i;
    mpz_t new_n, new_deep;

    mpz_init(new_n);
    mpz_init(new_deep);
    mpz_mul_ui(new_deep, deep, 10);

    if (mpz_cmp(m, n) < 0)
        mpz_set(m, n);

    for (i = 1; i < 10; ++i)
    {
        mpz_set(new_n, n);
        mpz_addmul_ui(new_n, new_deep, i);

        if (mpz_probab_prime_p(new_n, 20))
            dfs(new_n, new_deep);
    }

    mpz_clear(new_n);
    mpz_clear(new_deep);
}

int main(void)
{
    mpz_t n, deep;

    mpz_init(m);
    mpz_init(n);
    mpz_init(deep);
    mpz_set_ui(deep, 1);

    mpz_set_ui(n, 3);
    dfs(n, deep);
    mpz_set_ui(n, 5);
    dfs(n, deep);
    mpz_set_ui(n, 7);
    dfs(n, deep);

    mpz_out_str(stdout, 10, m);

    mpz_clear(deep);
    mpz_clear(n);
    mpz_clear(m);

    return 0;
}
/* cc: flags+='-lgmp' */

另外，其实这种东西用python写更方便，虽然需要自己实现MillerRabin……

#!/usr/bin/python
import random

def toBinary(n):
    r = []
    while (n > 0):
        r.append(n % 2)
        n = n / 2
    return r

def test(a, n):
    """
    Returns:
      - True, if n is complex.
      - False, if n is probably prime.
    """
    b = toBinary(n - 1)
    d = 1
    for i in xrange(len(b) - 1, -1, -1):
        x = d
        d = (d * d) % n
        if d == 1 and x != 1 and x != n - 1:
            return True
        if b[i] == 1:
            d = (d * a) % n
    if d != 1:
        return True # Complex
    return False # Prime

def MillerRabin(n, s = 15):
    """
      Returns:
        - True, if n is probably prime.
        - False, if n is complex.
    """
    for j in xrange(1, s + 1):
        a = random.randint(1, n - 1)
        if (test(a, n)):
            return False # n is complex
    return True # n is prime

def dfs(n, d):
    global m

    if m < n:
    m = n

    nd = d * 10

    for i in xrange(1, 10):
       nn = n + nd * i
       if MillerRabin(nn, 20):
           dfs(nn, nd)


m = 1
for i in [3,5,7]:
    dfs(i, 1)

print (m)

这个程序怎么才能在普通的Windows环境下编译通过？

http://topic.

善用搜索引擎