记录编号	2579	评测结果	AAAAAA
题目名称	[HAOI 2004模拟]数列问题	最终得分	100
用户昵称	cuixiaofei	是否通过	通过
代码语言	Pascal	运行时间	0.975 s
提交时间	2008-09-22 22:00:58	内存使用	0.12 MiB

//na                            :cuixiaofei;
//da                            :08_09_19;
program dfs3;
  var
    n,ge                        :longint;
    zhishu,ji,a                 :array[1..1000] of longint;
    f1,f2                       :text;
  procedure init;
  begin
    assign(f1,'dfs3.in');
    reset(f1);
    assign(f2,'dfs3.out');
    rewrite(f2);
    ge:=0;
    readln(f1,n);
    fillchar(ji,sizeof(ji),0);
  end;
  procedure zhaozhishu;
    var
      i,j                       :longint;
  begin
    for i:=1 to 1000 do
      zhishu[i]:=1;
    zhishu[1]:=0;
    for i:=2 to 1000 do
      if zhishu[i]=1 then
        begin
          for j:=i to 1000 div i do
            begin
              zhishu[i*j]:=0;
            end;
        end;
  end;

  procedure sousuo(k:longint);
    var
      i                         :longint;
  begin
    if k=n+1 then
      begin
        for i:=1 to n do
          write(f2,a[i],' ');
        writeln(f2);
        inc(ge);
      end
    else if k=1 then
      begin
        if n mod 2=0 then
          begin
            for i:=1 to n do
              if ji[i]=0 then
                begin
                  ji[i]:=1;
                  a[k]:=i;
                  sousuo(k+1);
                  ji[i]:=0;
                end;
          end
        else
          begin
            i:=1;
            while i<=n do
              begin
                if ji[i]=0 then
                  begin
                    ji[i]:=1;
                    a[k]:=i;
                    sousuo(k+1);
                    ji[i]:=0;
                  end;
                inc(i,2);
              end;
          end;
      end
    else
      begin
        if a[k-1] mod 2 =0 then
          i:=1
        else
          i:=2;
          while i<=n do
            begin
              if (ji[i]=0) and (zhishu[i+a[k-1]]=1) then
                begin
                  ji[i]:=1;
                  a[k]:=i;
                  sousuo(k+1);
                  ji[i]:=0;
                end;
              i:=i+2;
            end;
      end;
  end;

  procedure main;
  begin
    zhaozhishu;
    sousuo(1);
  end;
  procedure print;
  begin
    writeln(f2,ge);
    close(f1);
    close(f2);
  end;
  begin
    init;
    main;
    print;
  end.