Project Euler task 51

#include <iostream>
#include <vector>

// is_initialized, is_primary
std::vector<std::pair<bool, bool>> prime(10000000, { false, false });

bool isPrime(int n)
{
  if (n <= 1)
    return false;
  else if (n <= 3)
    return true;
  else if (n % 2 == 0 || n % 3 == 0)
    return false;

  if (prime[n].first)
    return prime[n].second;

  int x = sqrt(n) + 1;
  for (int i = 5; i <= x; i += 6)
    if (n % i == 0 || n % (i + 2) == 0)
    {
      prime[n].first = true;
      prime[n].second = false;
      return false;
    }

  prime[n].first = true;
  prime[n].second = true;

  return true;
}

bool nextPermutation(std::vector<int>& i_perest)
{
  int j = i_perest.size() - 2;
  while (j >= 0 && i_perest[j] >= i_perest[j + 1]) --j;
  if (j == -1)
    return false;

  int k = i_perest.size() - 1;
  while (i_perest[j] >= i_perest[k]) --k;
  std::swap(i_perest[j], i_perest[k]);

  int l = j + 1, r = i_perest.size() - 1;
  while (l < r)
    std::swap(i_perest[l++], i_perest[r--]);

  return true;
}

// The function takes the lambda to
// generate the numbers and number of
// digits in the number.
template <class T>
void genNumber(int order, T f)
{
  int ord = 1;
  std::vector<int> seq{ 1, 1, 1 };
  for (int j = 0; j < order; ++j)
  {
    seq.push_back(2);
    for (int i = ord; i < ord * 10; ++i)
    {
      int r = i % 10;
      if (r == 0 || r == 2 || r == 4 || r == 5 || r == 6 || r == 8)
        continue;

      if (!f(i, seq))
        return;
    }
    ord *= 10;
  }
}

// Input
// i_mask - vector mask to make substitution
// i_num - number to combine with
template <class T>
void substitute(const std::vector<int>& i_mask, int i_num, T f)
{
  for (int i = 0; i < 10; ++i)
  {
    if (i == 0 && i_mask.front() == 1)
      continue;

    int num = 0;
    int order = 1;
    int inp = i_num;

    for (int j = i_mask.size() - 1; j >= 0; --j)
    {
      if (i_mask[j] == 1)
        num += order * i;
      else
      {
        num += order * (inp % 10);
        inp /= 10;
      }

      order *= 10;
    }

    if (!f(num))
      break;
  }
}

int main()
{
  genNumber(4, [](int n, const std::vector<int>& mask){
    std::vector<int> cmask(mask);
    do
    {
      if (cmask.back() == 1)
        continue;

      int nonPrime = 0;
      int primes = 0;
      substitute(cmask, n, [&](int x){
        //std::cout << n << " " << x << " " << isPrime(x) << std::endl;
        if (!isPrime(x))
          ++nonPrime;
        else
          ++primes;

        if (nonPrime >= 3)
          return false;

        return true;
      });
      if (primes >= 8)
      {
        std::cout << "Found: ";
        substitute(cmask, n, [&](int x){
          std::cout << x << std::endl;
          return false;
        });
        return false;
      }
    } while (nextPermutation(cmask));

    return true;
  });

  return 0;
}