ac1025.pas

同济大学 Online在线题库 AC源代码合集 程序设计竞赛必看资料

program tju1025;
const
  maxn=10;
  maxsum=2*sqr(maxn)-1;
var
  prime:array[2..maxsum] of boolean;
  ans:array[1..maxn,1..maxn,1..maxn]of byte;
  next:array[0..sqr(maxn)]of byte;
  t,i,n,x,y:byte;
  finish:boolean;
procedure calprime;
  var
    i,t:byte;
  begin
    fillchar(prime,sizeof(prime),true);
    for i:=2 to trunc(sqrt(maxsum)) do begin
      if not prime[i] then continue;
      t:=i+i;
      while t<=maxsum do begin
        prime[t]:=false;
        inc(t,i);
      end;
    end;
  end;
procedure search(x,y:byte);
  var
    p,i:byte;
  begin
    p:=0;
    while next[p]>0 do begin
      i:=next[p];
      if ((x=1) or prime[i+ans[n,x-1,y]]) and ((y=1) or prime[i+ans[n,x,y-1]]) then begin
        ans[n,x,y]:=i;
        next[p]:=next[i];
        if y=n then
          if x=n then finish:=true else search(x+1,1)
        else
          search(x,y+1);
        next[p]:=i;
        if finish then exit;
      end;
      p:=i;
    end;
  end;
begin
  calprime;
  for n:=1 to maxn do begin
    for i:=sqr(n-1) to sqr(n)-1 do
      next[i]:=i+1;
    finish:=false;
    search(1,1);
    if not finish then ans[n,1,1]:=0;
  end;

  read(t);
  for i:=1 to t do begin
    read(n);
    if ans[n,1,1]=0 then
      writeln('NO')
    else
      for x:=1 to n do begin
        for y:=1 to n-1 do
          write(ans[n,x,y],' ');
        writeln(ans[n,x,n]);
      end;
  end;
end.