IBM Ponder this 2019 April

题意：找9个质数排成$3\times 3$幻方，使得每行、每列、每个对角线的平均数还是质数

显然所有数模$3$的余数相同

把模$3$余$2$的前$9$个质数找出来随便排排就能排出幻方了。。满足条件的解还挺多

字典序最小的解：\[\begin{matrix}5&11&17\\23&29&59\\41&47&53\end{matrix}\]

#include <bits/stdc++.h>
using namespace std;

int prime[12345];
void get() {
  int i, n = 10000;
  for (i = 2; i <= n; i++) prime[i] = 1;
  for (i = 2; i <= n; i++)
    if (prime[i])
      for (int j = i + i; j <= n; j += i) prime[j] = 0;
}

int p[12] = {5,11,17,23,29,41,47,53,59};

/* 0 1 2
   3 4 5
   6 7 8 */

int main() {
  get();
  do {
    if (p[0] < p[2] && p[0] < p[6] && p[0] < p[8] && p[2] < p[6])
      if (prime[(p[0]+p[1]+p[2])/3])
        if (prime[(p[3]+p[4]+p[5])/3])
          if (prime[(p[6]+p[7]+p[8])/3])
            if (prime[(p[0]+p[3]+p[6])/3])
              if (prime[(p[1]+p[4]+p[7])/3])
                if (prime[(p[2]+p[5]+p[8])/3])
                  if (prime[(p[0]+p[4]+p[8])/3])
                    if (prime[(p[2]+p[4]+p[6])/3]) {
                      printf("===========\n");
                      printf("%2d %2d %2d\n", p[0], p[1], p[2]);
                      printf("%2d %2d %2d\n", p[3], p[4], p[5]);
                      printf("%2d %2d %2d\n", p[6], p[7], p[8]);
                      printf("\n");
                    }
  } while (next_permutation(p, p + 9));
}