Editorial for Vòng số nguyên tố


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

const max=10000;
      re:array[1..9] of longint=(1,2,2,4,96,1024,2880,81024,770144);
var n:byte;
    dem:longint;
    a,t:array[1..20] of byte;
    d:array[2..20] of byte;
    prime:array[2..39] of byte;

procedure init;
var i,j:byte;
begin
     fillchar(prime,sizeof(prime),0);
     for i:=2 to 37 do
         if prime[i]=0 then
         begin
              j:=2*i;
              while j<=39 do
              begin
                   prime[j]:=1;
                   j:=j+i;
              end;
         end;
end;

procedure rf;
begin
     read(n);
end;

procedure att(i:byte);
var j,k:byte;
begin
     for j:=2 to 2*n do
     begin
          if (d[j]=0) and (prime[j+a[i-1]]=0) then
          begin
               a[i]:=j; d[j]:=1;
               if i<2*n then att(i+1)
               else
               begin
                    if prime[a[i]+1]=0 then
                    begin
                         for k:=1 to 2*n do write(a[k],' ');
                         writeln;
                         inc(dem);
                         if dem>max then break;
                    end;
               end;
               a[i]:=0; d[j]:=0;
          end;
     end;
end;

procedure pr;
var i,j:byte;
begin
     writeln(re[n]);
     fillchar(a,sizeof(a),0);
     fillchar(d,sizeof(d),0);
     init;
     dem:=1;
     a[1]:=1;
     att(2);
end;

begin
     rf;
     pr;
end.

Code mẫu của happyboy99x

#include <cstdio>

#define FOR(i, a, b) for( int i = (a), _b = (b); i <= _b; ++i )
#define REP(i, n) for( int i = 0, _n = (n); i < _n; ++i )

int n, pr[40], res[25], ch[40];
int tp[10005][25], count;

void eratos( int n ) {
        REP(i, n+1) pr[i] = 1;
        pr[0] = pr[1] = 0;
        int i = 2;
        while ( i * i <= n ) {
                for( int j = i + i; j <= n; j += i ) pr[j] = 0;
                do ++i; while( i * i <= n && !pr[i] );
        }
}

void backtrack( int k ) {
    if ( k == 2*n ) {
        if (pr[res[k-1] + res[0]]) {
            if ( count < 10000 )
                REP(i, k) tp[count][i] = res[i];
            count++;
        }
    } else  FOR(i, 1, 2*n) if ( !ch[i] && pr[res[k-1]+i] ) {
            res[k] = i; ch[i] = 1;
            backtrack(k+1);
            ch[i] = 0;
        }
}

int main() {
    eratos(39);
    scanf( "%d", &n );
    res[0] = 1; ch[1] = 1; count = 0;
    backtrack(1);
    printf( "%d\n", count );
    REP(i, count < 10000 ? count : 10000) {
        printf( "%d", tp[i][0] );
        FOR(j, 1, 2*n-1) printf( " %d", tp[i][j] );
        putchar('\n');
    }
    return 0;
}

Code mẫu của ladpro98

program pcircle;
uses    math;
const   a :array[1..9] of longint = (1,2,2,4,96,1024,2880,81024,770144);
var     res:array[1..20] of longint;
        check:array[1..20] of boolean;
        n,k:longint;
        done:boolean;


function isPrime(x:longint):boolean;
var     k,n:longint;
begin

        n:=x;
        if (n=2) or (n=3) or (n=5) or (n=7) then exit(true);
        if n mod 2 = 0 then exit(false);
        if (n mod 3 = 0) then exit(false);
        k:=0;

        while k<=trunc(sqrt(n)) do
        begin
                inc(k,6);
                if (n mod (k-1) = 0 ) or (n mod (k+1) = 0) then exit(false);
        end;
        isPrime:=true;
end;

procedure print;
var     i:longint;
begin
        for i:=1 to n do
        write(res[i],' ');
        writeln;
end;

procedure back(i,val:longint);
var     j:longint;
begin
        if done then exit;
        if i>n then
        begin
                if (isprime(val+res[1])) then
                begin
                        inc(k);
                        if k>10000 then done:=true
                        else
                        print;
                end;
                exit;
        end;
        for j:=1 to n do
        if (not check[j]) and isprime(val+j) then
        begin
                 check[j]:=true;
                 res[i]:=j;
                back(i+1,j);
                check[j]:=false;
        end;
end;

begin

        readln(n);
        fillchar(check,sizeof(check),false);
        k:=0;
        n:=2*n;
        res[1]:=1;
        check[1]:=true;
        writeln(a[n div 2]);
        back(2,1);

end.

Code mẫu của RR

const
  res:array[2..9] of longint=(2,2,4,96,1024,2880,81024,770144);
var
  used,p:array[1..40] of boolean;
  a:array[1..40] of longint;
  cnt,n,i:longint;

function isPrime(n:longint):boolean;
    var
      i:longint;
    begin
      for i:=2 to trunc(sqrt(n)) do
        if n mod i=0 then exit(false);
      exit(i>1);
    end;

procedure dequy(i:longint);
    var
      j,k:longint;
    begin
      if cnt>10000 then exit;
      for j:=2 to n shl 1 do
      if (not used[j]) and p[a[i-1]+j] then
        begin
          used[j]:=true;
          a[i]:=j;
          if i<n shl 1 then dequy(i+1)
          else if p[a[1]+a[i]] then
            begin
              inc(cnt);
              if cnt>10000 then exit;
              for k:=1 to n shl 1 do write(a[k],' ');
              writeln;
            end;
          used[j]:=false;
          if cnt>10000 then exit;
        end;
    end;

begin
  fillchar(used,sizeof(used),false);
  for i:=1 to 40 do p[i]:=isPrime(i);
  a[1]:=1; used[1]:=true;
  read(n); writeln(res[n]);
  dequy(2);
end.

Code mẫu của ll931110

Program PCIRCLE;
        Const
                input  = '';
                output = '';
        Var
                        a: array[1..20] of integer;
                   free,p: array[1..40] of boolean;
                     pnum: array[2..9] of longint;
                  n,c,num: longint;
                       fo: text;

Procedure init;
          Var
                fi: text;
          Begin
                Assign(fi, input);
                        Reset(fi);
                        Readln(fi, n);
                Close(fi);

                c:= n * 2;
                Fillchar(free, sizeof(free), true);

                a[1]:= 1;
                num:= 0;
          End;

Procedure printresult;
          Var
                i: integer;
          Begin
                For i:= 1 to c do write(fo, a[i],  ' ');
                Writeln(fo);
          End;

Procedure primearray;
          Begin
                Fillchar(p, sizeof(p), false);

                p[2]:= true;             p[17]:= true;
                p[3]:= true;             p[19]:= true;
                p[5]:= true;             p[23]:= true;
                p[7]:= true;             p[29]:= true;
                p[11]:= true;            p[31]:= true;
                p[13]:= true;
          End;

Procedure pnumber;
          Begin
                  pnum[2]:= 2;
                  pnum[3]:= 2;
                  pnum[4]:= 4;
                  pnum[5]:= 96;
                  pnum[6]:= 1024;
                  pnum[7]:= 2880;
                  pnum[8]:= 81024;
                  pnum[9]:= 770144;
          End;

Procedure attempt(t: integer);
          Var
                i: integer;
          Begin
                For i:= 2 to c do
                        If free[i] and p[i + a[t - 1]] then
                                Begin
                                        a[t]:= i;
                                        free[i]:= false;

                                        If (t = c) and p[a[c] + a[1]] then
                                                Begin
                                                        inc(num);
                                                        If num <= 10000 then printresult else exit;
                                                End
                                                        else attempt(t + 1);

                                        free[i]:= true;
                                End;
          End;

Begin
        init;
        primearray;

        Assign(fo, output);
                Rewrite(fo);
                        pnumber;
                        Writeln(fo, pnum[n]);
                        attempt(2);
        Close(fo);
End.

Code mẫu của khuc_tuan

#include "iostream"
#include "stdio.h"

using namespace std;

int n;
int a[22];
bool ngto[100];
bool dd[100];
int socach;

void duyet(int i, bool in) {
    if(in && socach>=10000) return;
    if(i==2*n) {
        if(ngto[a[2*n-1]+a[0]]) {
            ++socach;
            if(in && socach<=10000) {
                for(int i=0;i<2*n;++i) printf("%d ",a[i]);
                printf("\n");
            }
        }
        return;
    }

    for(int x=1;x<=2*n;++x) if(ngto[x+a[i-1]] && !dd[x]) {
        dd[x] = true;
        a[i] = x;
        duyet(i+1,in);
        dd[x] = false;
    }
}

void init() {
    memset( ngto, true, sizeof(ngto));
    ngto[0] = ngto[1] = false;
    for(int i=2;i<100;++i) {
        if(ngto[i]) {
            for(int j=i+i;j<100;j+=i) ngto[j] = false;
        }
    }
}

int main() {
    scanf("%d",&n);
    a[0] = 1;
    dd[1] = true;
    init();
    duyet(1, false);
    printf("%d\n", socach);
    socach = 0;
    duyet(1, true);
    return 0;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.