// If you’re factoring a number by trial division, you only need to
// try prime factors.  But knowing which numbers are prime is kind of
// a pain in the ass, and doing that for numbers up to 2³² requires a
// large table.  So maybe we can get a good speedup by just testing
// factors that *might* be prime.

// If n % 6 == 4, n cannot be prime, because it is divisible by 2 but
// is not 2, because 6 is also divisible by 2.  Similarly if n % 12 ==
// 6 or 9.  The residues mod 12 that might be prime are 1, 2, 3, 5, 7,
// and 11.  But 2 and 3 are only prime the first time; numbers like
// 14, 15, 26, and 27 are multiples of 2 and 3.  If we look n % 30 up
// in a table, we should be able to eliminate all the multiples of 2,
// 3, and 5, or anyway most of them.

// So the basic strategy is to pick a divisor that allows us to
// eliminate as many numbers as possible.

#include <stdio.h>

enum { wheelsize = 2*3*5*7*11*13 }; // 30030


int gcd(int a, int b)
{
  while (a) {
    //fprintf(stderr, "%d %d\n", a, b);
    int tmp = a;
    a = b % a;
    b = tmp;
  }
  return b;
}

int main()
{
  printf("#include <stdio.h>\n"
         "enum { wheelsize = %d };\n"
         "const int wheel[] = { 1, ",
         wheelsize);
  for (int i = 2; i < wheelsize; i++) {
    if (wheelsize % i == 0 || gcd(i, wheelsize) == 1) printf("%d, ", i);
  }

  return 0;
}