BÀI TẬP 61: SỐ SIÊU NGUYÊN TỐ

Số siêu nguyên tố là số nguyên tố mà khi bỏ một số tuỳ ý các chữ số bên phải của nó thì phần còn lại vẫn tạo thành một số nguyên tố.

            Ví dụ: 7331 là một số siêu nguyên tố có 4 chữ số, vì 733, 73, 7 cũng là các số nguyên tố.

            Em hãy viết chương trình tìm các số siêu nguyên tố có N chữ số (0<N<10) và số lượng các số tìm được.

            Dữ liệu vào: cho trong File SIEUNT.INP chứa số N.

            Kết quả: ghi ra file SIEUNT.OUT gồm các dòng:

            - Dòng 1: số lượng các số siêu nguyên tố có N chữ số.

            - Dòng tiếp theo: liệt kê các số siêu nguyên tố tìm được (hiển thị 3 số trên 1 dòng).

            Ví dụ:

SIEUNT.INP	SIEUNT.OUT
4	16 2333 2339 2393 2399 2939 3119 3137 3733 3739 3793 3797 5939 7193 7331 7333 7393

    - Cách làm: 

    + Xây dựng cấu hình (X1,X2,..,Xn) 

    + Khi ta xóa dần các chữ số bên phải thì số còn lại vẫn là số nguyên tố 

    + Như vậy khi số còn lại một chữ số thì số còn lại vẫn là số nguyên tố: như vậy ta biết được X1 trong cấu hình chắc chắn sẽ nhận các giá trị 2,3,5,7 

    + Tiếp tục khi ta ghép các số bên phải thì số đó cũng là số nguyên số nên: X2,..,Xn có thể nhận các giá trị 1,3,7,9 

    + Khi x1 nhận lầm lượt 2,3,5,7 

    + Ta thử X2 nhận lần lượt 1,3,7,9 Nếu X1*10+X2 là số nguyên tố thì ta đi thử X3 nhận lần lượt 1,3,7,9 ..... Ta thử đến Xn 

    + In cấu hình tìm được (X1,X2,..,Xn) ta được một số siêu nguyên tố

    CODE THAM KHẢO:

program Sieu_Nguyen_To;

var d,j,n,nt: longint;

    Luu:array[1..100] of longint;

    X1, X2: array[1..10] of longint;

    fi, fo: text;

procedure Khoitao;

begin

        assign(fi, 'SIEUNT.INP'); reset(fi);

        readln(fi,n);

        X1[1]:=2; X1[2]:=3; X1[3]:=5; X1[4]:=7; d:=0;

        X2[1]:=1; X2[2]:=3; X2[3]:=7; X2[4]:=9;

        close(fi);

end;

function NgTo(M: longint): boolean;

var S,K: longint;

begin

        NgTo:=True;

        for k:=2 to trunc(sqrt(M)) do

          if M mod k = 0 then exit(False);

end;

procedure Try(i:byte);

var j:byte;

begin

        for j:=1 to 4 do

        begin

                NT:=NT*10+X2[j];

                if NgTo(NT) then

                  if i=N then

                     begin

                        inc(d); Luu[d]:=NT;

                     end

                  else  Try(i+1);

                NT:=NT div 10;

        end;

end;

begin

        Khoitao;

        assign(fo,'SIEUNT.OUT'); rewrite(fo);

        for j:=1 to 4 do

        begin

                NT:=X1[j]; Try(2);

        end;

        write(fo,d);

        for j:=1 to d do

        begin

                if j mod 3 = 1 then writeln(fo);

                write(fo,Luu[j],' ');

        end;

        close(fo);

end.