Bài lập trình khá rắc rối

[megamanxza]

[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

Một số tự nhiên được gọi là số nguyên tố đặc biệt khi xoá bớt từng chữ số bên trái thì số còn lại vẫn là số nguyên tố. VD: 86311 là số nguyên tố đặc biệt vì 86311, 6311, 311, 11 đều là số nguyên tố. Hãy viết chương trình nhập vào số N (1<N\leq9) và in ra màn hình số các số nguyên tố đặc biệt có N chữ số ở dạng trên.
VD: Nhap vao N=5
Co tat ca 359 so nguyen to dac biet co 5 chu so!

Các bạn khi giải bài này hãy trình bày ra dạng bài lập trình Pascal nha! Thanks trước nhá!

 

[englandhuynh]

Test với n = 2 thì đúng, còn n lớn hơn không có điều kiện test

USES crt;
VAR
    n:BYTE;
    s:STRING;   
    kq:WORD;
    
FUNCTION nt(sinp:STRING):BOOLEAN;
VAR
    i,tmp:BYTE;
BEGIN
    val(sinp,tmp);
    FOR i:=2 TO trunc(sqrt(tmp)) DO
        IF tmp MOD i = 0 THEN exit(FALSE);
   exit(TRUE);
END;

PROCEDURE Attempt(i:BYTE);
VAR 
    j:CHAR;
BEGIN
    FOR j:='1' TO '9' DO 
       IF nt(j+s) THEN
            BEGIN
                s:=j+s;
                IF i=n THEN BEGIN inc(kq); writeln(s); END
                ELSE Attempt(i+1);
                delete(s,1,1);
            END;   
END;
BEGIN        
clrscr;
    write('N = ');readln(n);
    s:=''; kq:=0;
    Attempt(1);  
    write(' So cac so thoa man la : ',kq); 
readln
END.

 

[mikelhpdatke]

Mình làm test số nhỏ thì đúng rùi, số n=5 test thì nhỏ hơn vs ví dụ. Thuận toán của mình là quay lui rồi tăng tổng, pro nào vào xem có sai sót j ko ?

USES crt;
VAR
    n:BYTE;
    s:STRING;   
    kq:WORD;
    
FUNCTION nt(sinp:STRING):BOOLEAN;
VAR
    i,tmp:BYTE;
BEGIN
    val(sinp,tmp);
    FOR i:=2 TO trunc(sqrt(tmp)) DO
        IF tmp MOD i = 0 THEN exit(FALSE);
   exit(TRUE);
END;

PROCEDURE Attempt(i:BYTE);
VAR 
    j:CHAR;
BEGIN
    FOR j:='1' TO '9' DO 
       IF nt(s+j) THEN
            BEGIN
                s:=s+j;
                IF i=n THEN inc(kq)
                ELSE Attempt(i+1);
                delete(s,length(s),1);
            END;   
END;
BEGIN        
clrscr;
    write('N = ');readln(n);
    s:=''; kq:=0;
    Attempt(1);  
    write(kq); 
readln
END.

Dùng sàng Eratosthenes đi bạn trẻ . Duyệt kiểm tra đến bao giờ )

 

[englandhuynh]

@Mikel : Dùng sàng thì tốn khâu sàng rồi khâu kiểm tra xem có thỏa mãn không , còn dùng quay lui thì kiểm tra nếu thêm 1 số vào trước nếu nó thỏa mãn thì tìm thêm các số trước nó đến đủ n số, thật ra đây không phải là duyệt nó chỉ là sinh ra các số thỏa mãn thôi. Nói chung là dùng sàng nguyên tố hay quay lui đều phải tìm ra các số thỏa mãn mới ra được kết quả nên cũng như nhau thôi. Nếu có tối ưu hơn nữa thì tìm thuật toán bỏ qua bước sinh số .

p/s: chú code thử xem rồi test kết quả, thấy thuật toán không sai, test n=2 vẫn đúng nhưng test với n=5 của bác chủ thread thì kết quả lớn hơn nhiều :-?