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>
       
 
       
// find largest prime factor of each number up to "limit"

       
std::vector<unsigned int> largestPrime;
       
 
       
// fill "largestPrime"

       
void findLargestPrimes(unsigned int limit)
       
{
       
  largestPrime.resize(limit + 1, 1);
       
  for (unsigned long long i = 2; i <= limit; i++)
       
  {
       
    // skip if i is not a prime
       
    if (largestPrime[i] > 1)
       
      continue;
       
 
       
    // modify all multiples
       
    for (auto j = i; j <= limit; j += i)
       
      largestPrime[j] = i;
       
 
       
    // and all exponents i^2, i^3, i^4, ...
       
    auto j = i * i;
       
    while (j <= limit)
       
    {
       
      largestPrime[j] = j;
       
      j *= i;
       
    }
       
  }
       
}
       
 
       
// find maximum a that solves a^2 == a mod n

       
unsigned int search(unsigned int n)
       
{
       
  // don't forget about that special case n = 1 ...
       
  if (n == 1)
       
    return 0;
       
 
       
  // always return 1 if n has only one prime factor (is prime or perfect power of a prime, e.g. 32 = 2^5)
       
  auto p = largestPrime[n];
       
  if (p == n)
       
    return 1;
       
 
       
  // largest multiple of n's largest prime factor
       
  auto start = n - (n % p);
       
  // go backwards through all multiples of step
       
  for (unsigned long long x = start; x >= p; x -= p)
       
  {
       
    // check a - 1 = x which is a = x + 1
       
    auto next = x + 1;
       
    if ((next * next) % n == next)
       
      return next;
       
 
       
    // check a
       
    if ((x * x) % n == x)
       
      return x;
       
  }
       
 
       
  return 1;
       
}
       
 
       
// simple algorithm (pretty slow)

       
unsigned int slow(unsigned int n)
       
{
       
  unsigned long long a = n - 1;
       
  while (a >= 1)
       
  {
       
    // found a solution ?
       
    if ((a * a) % n == a)
       
      break;
       
 
       
    // no, keep going ...
       
    a--;
       
  }
       
 
       
  return a;
       
}
       
 
       
int main()
       
{
       
  unsigned int limit = 10000000;
       
  std::cin >> limit;
       
 
       
  // find largest prime factor of each number up to "limit"
       
  findLargestPrimes(limit);
       
 
       
  unsigned long long sum = 0;
       
  for (unsigned int n = 1; n <= limit; n++)
       
  {
       
    //auto current = slow(n);
       
    auto current = search(n);
       
    sum += current;
       
  }
       
 
       
  // display result
       
  std::cout << sum << std::endl;
       
  return 0;
       
}

This solution contains 16 empty lines, 18 comments and 2 preprocessor commands.