C++ "almost" solution to Project Euler 111

111.cpp

#include <stdio.h>
#include <assert.h>
#include <math.h>

struct prime {
  int32_t value;
  prime* next;
};
prime primes = { 2, NULL };
prime* tail = &primes;

int32_t candidate = 5;
int32_t step = 4;

void push(int32_t n) {
  prime* const p = (prime*)calloc(1, sizeof(prime));
  tail->next = p;
  *p = (prime){ n, NULL };
  tail = p;
}

bool is_prime(int64_t n);

int main() {
  push(3);
  push(5);

  assert( is_prime( 3));
  assert(!is_prime( 4));
  assert( is_prime( 5));
  assert(!is_prime( 6));
  assert( is_prime( 7));
  assert(!is_prime( 8));
  assert(!is_prime( 9));
  assert(!is_prime(10));
  assert( is_prime(11));

  const int32_t n = 6;

  int64_t r = 0;
  for (int i = 0; i <= 9; ++i) {
    int64_t s = 0;
    int32_t g = 2;
    int64_t x = pow(10, n - 1) - 1;
    int64_t temp = pow(10, n);
    while (x < temp) {
      int64_t z = x += 2;
      int32_t m = 0;
      while (z) {
        if (i == z % 10) ++m;
        z /= 10;
      }
      if (g > m) continue;
      if (!is_prime(x)) continue;
      if (m <= g) {
        s += x;
        continue;
      }
      s = x;
      g = m;
    }
    r += s;
  }

  printf("%lld\n", r);

  printf("OK\n");
}

bool is_prime(int64_t n) {
  const prime* p;
  for (p = &primes; p; p = p->next) {
    if (n % p->value == 0) return false;
    if (n <= p->value * p->value) return true;
  }
  for (;;) {
    for (;;) {
      candidate += step = 6 - step;
      for (p = &primes; p; p = p->next) {
        if (candidate % p->value == 0) break;
        if (candidate <= p->value * p->value) goto A;
      }
      assert(p);
    }
    A:;
    push(candidate);
    if (n % candidate == 0) return false;
    if (n <= candidate * candidate) return true;
  }
  assert(0);
}