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 <set>
       
#include <cmath>
       
 
       
// ---------- 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) + 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 ----------

       
 
       
// (0,0) is located in the upper-left corner

       
struct Board
       
{
       
  typedef unsigned int Number;
       
  // position of the red counter
       
  Number redX, redY;
       
  // empty square
       
  Number emptyX, emptyY;
       
 
       
  Board(Number redX_, Number redY_, Number emptyX_, Number emptyY_)
       
  : redX(redX_), redY(redY_), emptyX(emptyX_), emptyY(emptyY_)
       
  {}
       
 
       
  // for std::set
       
  bool operator<(const Board& other) const
       
  {
       
    if (redX   != other.redX)   return redX   < other.redX;
       
    if (redY   != other.redY)   return redY   < other.redY;
       
    if (emptyX != other.emptyX) return emptyX < other.emptyX;
       
    return emptyY < other.emptyY;
       
  }
       
};
       
 
       
// breadth-search

       
unsigned int bruteForce(unsigned int width, unsigned int height)
       
{
       
  // ensure width >= height
       
  if (width < height)
       
    std::swap(width, height);
       
 
       
  // start with the red counter in the upper-left corner and empty square in lowe-right corner
       
  Board initial(0,0, width-1,height-1);
       
  std::vector<Board> todo = { initial };
       
  std::set<Board> visited = { initial };
       
 
       
  unsigned int depth = 0;
       
  while (!todo.empty())
       
  {
       
    std::vector<Board> next;
       
    for (auto current : todo)
       
    {
       
      // finished ?
       
      if (current.redX == width - 1 && current.redY == height - 1)
       
        return depth;
       
 
       
      // "move" the empty square, ignore already visited positions
       
      // right
       
      if (current.emptyX + 1 < width)
       
      {
       
        Board right = current;
       
        right.emptyX++;
       
        // move red counter ?
       
        if (right.emptyX == right.redX && right.emptyY == right.redY)
       
          right.redX--;
       
        // if unvisited yet, then add to queue for next iteration
       
        if (visited.count(right) == 0)
       
        {
       
          next.push_back(right);
       
          visited.insert(right);
       
        }
       
      }
       
      // left
       
      if (current.emptyX > 0)
       
      {
       
        Board left = current;
       
        left.emptyX--;
       
        // move red counter ?
       
        if (left.emptyX == left.redX && left.emptyY == left.redY)
       
          left.redX++;
       
        // if unvisited yet, then add to queue for next iteration
       
        if (visited.count(left) == 0)
       
        {
       
          next.push_back(left);
       
          visited.insert(left);
       
        }
       
      }
       
      // down
       
      if (current.emptyY + 1 < height)
       
      {
       
        Board down = current;
       
        down.emptyY++;
       
        // move red counter ?
       
        if (down.emptyX == down.redX && down.emptyY == down.redY)
       
          down.redY--;
       
        // if unvisited yet, then add to queue for next iteration
       
        if (visited.count(down) == 0)
       
        {
       
          next.push_back(down);
       
          visited.insert(down);
       
        }
       
      }
       
      // up
       
      if (current.emptyY > 0)
       
      {
       
        Board up = current;
       
        up.emptyY--;
       
        // move red counter ?
       
        if (up.emptyX == up.redX && up.emptyY == up.redY)
       
          up.redY++;
       
        // if unvisited yet, then add to queue for next iteration
       
        if (visited.count(up) == 0)
       
        {
       
          next.push_back(up);
       
          visited.insert(up);
       
        }
       
      }
       
    }
       
 
       
    // next iteration
       
    todo = std::move(next);
       
    depth++;
       
  }
       
 
       
  // unsolvable grid
       
  return 0; // never reached
       
}
       
 
       
// just a bit of pattern matching until it produced the same results as bruteForceSlow()

       
unsigned int search(unsigned int width, unsigned int height)
       
{
       
  // ensure width >= height
       
  if (width < height)
       
    std::swap(width, height);
       
 
       
  // small grids are impossible
       
  if (width <  2)
       
    return 0;
       
  // precalculated results for 2x2, 3x2 and 3x3
       
  if (width == 2)
       
    return 5;
       
  if (width == 3)
       
    return height == 2 ? 9 : 13;
       
 
       
  // result for height = 2
       
  auto two  = 6 * width - 9;
       
  // and adjust for arbitrary height
       
  auto full = two + 2 * height - 4;
       
  // two more moves required if both sides are equal
       
  if (width == height)
       
    full += 2;
       
 
       
  return full;
       
}
       
 
       
int main()
       
{
       
  unsigned int limit = 1000000;
       
  std::cin >> limit;
       
 
       
  // verify the two drawings
       
  //std::cout << bruteForce(2, 2) << std::endl;
       
  //std::cout << bruteForce(5, 4) << std::endl;
       
 
       
  // generate enough prime numbers
       
  fillSieve(limit);
       
 
       
//#define VERIFY_100

       
#ifdef  VERIFY_100
       
  // use faster bruteForce() function to verify S(100)
       
  for (unsigned int current = 2; current <= limit; current++)
       
  {
       
    if (!isPrime(current))
       
      continue;
       
 
       
    unsigned int sum = 0;
       
 
       
    // verify the larger dataset p^2 where p is a prime and p < 100
       
    for (unsigned int width = 2; search(width, 2) <= current*current; width++)
       
      for (unsigned int height = 2; height <= width; height++)
       
      {
       
        auto steps = search(width, height);
       
        // too large ?
       
        if (steps > current * current)
       
          break;
       
 
       
        // is it a square of a prime ?
       
        unsigned int root = sqrt(steps);
       
        if (root * root != steps || !isPrime(root))
       
          continue;
       
 
       
        // found one more solution
       
        sum++;
       
        // symmetry: if (m,n) is a solution then (n,m) is a solution, too
       
        if (width != height)
       
          sum++;
       
      }
       
 
       
    // display result
       
    std::cout << "S(" << current << ")=" << sum << std::endl;
       
  }
       
#endif
       
 
       
  // fast algorithm
       
  unsigned long long sum = 0;
       
  for (unsigned int p = 2; p <= limit; p++)
       
  {
       
    if (!isPrime(p))
       
      continue;
       
 
       
    // increment is (p^2 - 1) / 12
       
    // need 64 bit for p^2
       
    auto square    = (unsigned long long) p * p;
       
    auto increment = (square - 1) / 12;
       
    // except if p=3
       
    if (p == 3)
       
      sum += 2;
       
    else
       
      sum += increment;
       
  }
       
 
       
  // finally ...
       
  std::cout << sum << std::endl;
       
  return 0;
       
}

This solution contains 33 empty lines, 60 comments and 6 preprocessor commands.