My code

… was written in C++11 and can be compiled with G++, Clang++, Visual C++. You can download it, too. Or just jump to my GitHub repository.

       
#include <iostream>
       
#include <vector>
       
#include <queue>
       
#include <unordered_map>
       
#include <algorithm>
       
#include <functional>
       
 
       
// ---------- standard prime sieve from my toolbox

       
 
       
// odd prime numbers are marked as "true" in a bitvector

       
std::vector<bool> sieve;
       
 
       
// return true, if x is a prime number

       
bool isPrime(unsigned int x)
       
{
       
  // handle even numbers
       
  if ((x & 1) == 0)
       
    return x == 2;
       
 
       
  // lookup for odd numbers
       
  return sieve[x >> 1];
       
}
       
 
       
// find all prime numbers from 2 to size

       
void fillSieve(unsigned int size)
       
{
       
  // store only odd numbers
       
  const unsigned int half = size >> 1;
       
 
       
  // allocate memory
       
  sieve.resize(half, true);
       
  // 1 is not a prime number
       
  sieve[0] = false;
       
 
       
  // process all relevant prime factors
       
  for (unsigned int i = 1; 2 * i*i < half; i++)
       
    // do we have a prime factor ?
       
    if (sieve[i])
       
    {
       
      // mark all its multiples as false
       
      unsigned int current = 3 * i + 1;
       
      while (current < half)
       
      {
       
        sieve[current] = false;
       
        current += 2 * i + 1;
       
      }
       
    }
       
}
       
 
       
// ---------- problem specific code ----------

       
 
       
typedef std::unordered_map<unsigned int, std::vector<unsigned int>> Edges;
       
// create graph

       
Edges findEdges(unsigned int limit)
       
{
       
  Edges connected;
       
  // pre-allocate some memory
       
  connected.reserve(limit / 10);
       
 
       
  for (unsigned int i = 2; i < limit; i++)
       
  {
       
    if (!isPrime(i))
       
      continue;
       
 
       
    const unsigned int MaxPos = 7;
       
    // split i into its digits but keep their ten's exponents
       
    // e.g. 1234 => split = { 4, 30, 200, 1000, 0, 0, 0 };
       
    unsigned int split[MaxPos] = { 0,0,0,0,0,0,0 };
       
    unsigned int shift = 1;
       
    auto reduced = i;
       
    for (unsigned int pos = 0; pos < MaxPos; pos++)
       
    {
       
      shift *= 10;
       
      split[pos] = reduced % shift;
       
      reduced   -= reduced % shift;
       
    }
       
 
       
    shift = 1;
       
    for (unsigned int pos = 0; shift < 10*i && shift < limit; pos++, shift *= 10)
       
    {
       
      auto current = i;
       
 
       
      // analyze all bigger numbers
       
      for (unsigned int digit = split[pos] + shift; digit <= 9 * shift; digit += shift)
       
      {
       
        current += shift;
       
        if (isPrime(current))
       
        {
       
          // add if not existing (A => B)
       
          if (std::find(connected[i].begin(), connected[i].end(), current) == connected[i].end())
       
            connected[i].push_back(current);
       
 
       
          // add if not existing (B => A)
       
          if (std::find(connected[current].begin(), connected[current].end(), i) == connected[current].end())
       
          {
       
            // pre-allocate some memory
       
            connected[current].reserve(8);
       
            connected[current].push_back(i);
       
          }
       
        }
       
      }
       
    }
       
  }
       
 
       
  return connected;
       
}
       
 
       
typedef std::unordered_map<unsigned int, unsigned int> Best;
       
// return the minimized highest number between 2 and every prime

       
Best findLowestPaths(const Edges& connected)
       
{
       
  // best[x] is the lowest number on the path between 2 and x
       
  Best best;
       
 
       
  std::priority_queue<unsigned int, std::vector<unsigned int>, std::greater<unsigned int> > todo;
       
  todo.push(2);
       
 
       
  while (!todo.empty())
       
  {
       
    auto current = todo.top();
       
    todo.pop();
       
 
       
    // highest number so far
       
    auto top = best[current];
       
    // include current number, too
       
    if (top < current)
       
      top = current;
       
 
       
    auto connections = connected.find(current);
       
    if (connections == connected.end())
       
      continue;
       
 
       
    for (auto edge : connections->second)
       
    {
       
      auto high = best[edge];
       
      // no path or a worse path ?
       
      if (high == 0 || top < high)
       
      {
       
        // update with best value so far
       
        best[edge] = top;
       
 
       
        // re-evaluate
       
        todo.push(edge);
       
      }
       
    }
       
  }
       
 
       
  return best;
       
}
       
 
       
int main()
       
{
       
  unsigned int limit = 10000000;
       
  std::cin >> limit;
       
 
       
  // generate enough primes
       
  fillSieve(limit);
       
 
       
  // create graph
       
  auto connected = findEdges(limit);
       
 
       
  // find best path from 2 to each prime
       
  auto best = findLowestPaths(connected);
       
 
       
  // count primes with a connection to 2
       
  // or a path containing too high numbers
       
  unsigned long long result = 0;
       
  for (unsigned int i = 3; i < limit; i += 2)
       
    if (isPrime(i) && (best[i] == 0 || best[i] > i))
       
      result += i;
       
 
       
  // that's it !
       
  std::cout << result << std::endl;
       
  return 0;
       
}

This solution contains 29 empty lines, 34 comments and 6 preprocessor commands.