Giải bài số siêu nguyên tố

Tiêu đề: Giải bài số siêu nguyên tố Sun 28 Mar 2010, 13:46

Đề:

Trích dẫn :: Một số gọi là số siêu nguyên tố nếu số đó là số nguyên tố và nếu ta bỏ đi 1 số chữ số ở bene phải của số đó thì số còn lại vẫn là số nguyên tố.

Ví dụ 233 là số siêu nguyên tố có 3 chữ số vì 233 là số nguyên tố, 23 và 2 cũng là các số nguyên tố. Tương tự số 23 cũng là số siêu nguyên tố có 2 chữ số. Tuy nhiên 2 ko gọi là số sieue nguyên tố.

Hãy lập một chương trình đưa ra các số siêu nguyên tố có n chữ số nhập từ bàn phím với n<=9.

Mời các bạn tham gia cho vui.

Bài giải bằng đệ quy:

Code:: program so_sieu_nguyen_to;
uses crt;
var k,n:longint; dem:integer;

procedure nhap;
begin
clrscr;
repeat
write('nhap n: ');readln(n);
until (n>=1)and(n<=8);
k:=0;dem:=0;
end;

function ktnt(k:longint):boolean;
var i:longint;
begin
ktnt:=true;
if k<=1 then begin ktnt:=false; exit; end;
if (k mod 2=0)and(k>2) then begin ktnt:=false; exit; end;
i:=3;
while i<=trunc(sqrt(k)) do
begin
if k mod i=0 then begin ktnt:=false; exit; end;
i:=i+2;
end;
end;

procedure try(j:integer);
var l:integer;
begin
for l:=1 to 9 do
begin
k:=k*10+l;
if ktnt(k) then
if j=n then begin inc(dem); writeln('so thu ',dem,': ',k);end
else try(j+1);
k:=k div 10;
end;
end;

begin
nhap;
try(1);
writeln('Co ',dem,' so sieu nguyen to co ',n,' chu so.');
readln;
end