Luyện tập từ các đề thi Số nguyên tố cùng độ cao Olimpic Duy Tân 2009 Độ cao của một số tự nhiên là tổng các chữ số của số đó. Với mỗi cặp số tự nhiên n và h cho trước hãy liệt kê các số nguyên tố không vượt quá n và có độ cao h | Chương 5 Luyện tập từ các đề thi Số nguyên tố cùng độ cao Olimpic Duy Tân 2009 Độ cao của một số tự nhiên là tổng các chữ số của số đó. Với mồi cặp số tự nhiên n và h cho trước hãy liệt kê các số nguyên tố không vượt quá n và có độ cao h 10 n 1000000 1 h 54. n h mỗi dòng 1 số Dữ liệu test n 1000 h 16. Kết quả 15 số nguyên tố độ cao 16 79 97 277 349 367 439 457 547 619 673 691 709 727 853 907. Thuật toán Thuật toán liệt kê các số nguyên tố độ cao h trong khoảng 1. Gọi thủ tục Sang n do Eratosthenes đề xuất xem Tập 2 xác định các số nguyên tố trong khoảng và đánh dấu vào mảng byte p p i 0 khi và chỉ khi i là số nguyên tố. 2. Duyệt lại các số nguyên tố i trong danh sách p tính độ cao của số i. Nếu Height i h thì ghi nhận. 3. end. Để tính độ cao của số i ta tách dần các chữ số hàng đơn của i bằng phép chia dư cho 10 rồi cộng dồn vào một biến tổng. Độ phức tạp Thủ tục sàng duyệt vn lần mỗi lần lại duyệt n phần tử do đó cần cỡ n thao tác cơ sở phép nhân phép gán . Chương trình - So nguyen to cung do cao uses crt const fn gn nl 13 10 bl 32 mn 1000000 type mb1 array of byte var p mb1 n h longint procedure Sang n longint var i j longint begin fillchar p sizeof p 0 for i 2 to round sqrt n do if p i 0 then for j i to n div i do p i j 1 end function Height x longint integer var sum integer begin sum 0 while x 0 do begin sum sum x mod 10 x x div 10 end Height sum end procedure Ghi var i longint G text begin assign g gn rewrite g for i 2 to n do if p i 0 then if Height i h then writeln g i close g end procedure Doc var f text begin assign f fn reset f readln f n h close f end BEGIN Doc Sang n Ghi writeln nl Fini readln END. DevC - So nguyen to cung do cao include include fstream include iostream include include using namespace std D A T A A N D V A R I A B L E const int mn 1000001 char p mn int n h const char fn const char gn P R O T O T Y P E
