SKKN Áp dụng thuật toán sàng nguyên tố để giải một số bài tập về số nguyên tố trong Tin học nhằm nâng cao chất lượng bồi dưỡng học sinh giỏi ở trường trung học phổ thông 4 Thọ Xuân

1. PHẦN MỞ ĐẦU
1.1. Lý do chọn đề tài
 Công tác bồi dưỡng học sinh giỏi là một công tác mũi nhọn trong việc nâng cao chất lượng giáo dục, tạo nguồn lực, bồi dưỡng nhân tài cho nhà trường nói riêng, cho địa phương nói chung. Đồng thời, thông qua kết quả học sinh giỏi phần nào khẳng định được vị thế của trường so với các trường bạn trong huyện nói riêng và trong tỉnh nói chung.
Bồi dưỡng học sinh giỏi là một công việc khó khăn và lâu dài, đòi hỏi nhiều công sức của thầy và trò. Đặc biệt là những trường có chất lượng đầu vào của học sinh thấp nhất huyện như trường chúng tôi thì giấc mơ để học sinh có giải trong các kì thi học sinh giỏi Tỉnh là quá xa vời. 
Chất lượng học sinh giỏi môn Tin học của trường từ năm học 2011 – 2012 trở về trước là rất thấp, môn Tin học luôn trong tình trạng “trắng bảng”, chưa có học sinh nào đạt được giải học sinh giỏi môn Tin học cấp tỉnh, mặc dù một số năm vẫn có học sinh tham gia thi. Chất lượng học sinh giỏi môn Tin học còn thấp như vậy, phần vì năng lực học sinh, phần vì phương pháp giảng dạy của giáo viên chưa phù hợp. Do đó việc nâng cao chất lượng học sinh giỏi môn Tin học là cần thiết và cấp bách nhằm góp thêm vào thành tích chung của nhà trường.
Mặt khác, trong quá trình dạy bồi dưỡng học sinh giỏi tôi gặp rất nhiều bài toán về số nguyên tố. Đây là dạng bài tập không khó và thường xuất hiện trong các đề thi học sinh giỏi môn Tin học. Tuy nhiên rất nhiều học sinh khi gặp dạng bài tập này bị mất điểm hoặc điểm không cao. Nguyên nhân có thể nhiều nhưng trong đó có nguyên nhân cơ bản là: chương trình cho kết quả output sai hoặc chương trình cho kết quả output đúng nhưng chỉ với các bộ input có dữ liệu nhỏ còn với những bộ input có dữ liệu lớn thì chương trình chạy quá thời gian quy định mặc dù kết quả output vẫn đúng.
Với mong muốn giúp học sinh giải quyết tốt hơn các bài tập về số nguyên tố và hiểu biết sâu sắc hơn cách sử dụng giải thuật sàng nguyên tố, tôi đã dày công nghiên cứu, tìm tòi các bài tập có nội dung liên quan cũng như các đề thi của các tỉnh, trăn trở để tìm ra nhiều cách làm để học sinh biết các vận dụng để chương trình tối ưu nhất và dễ hiểu nhất. Từ đó nâng cao chất lượng bồi dưỡng học sinh giỏi môn Tin học.
Từ những lý do trên tôi đã mạnh dạn trình bày sáng kiến kinh nghiệm: “Áp dụng thuật toán sàng nguyên tố để giải một số bài tập về số nguyên tố trong Tin học nhằm nâng cao chất lượng bồi dưỡng học sinh giỏi ở trường trung học phổ thông 4 Thọ Xuân” để học sinh dễ dàng làm quen, tiếp thu và hình thành các kỹ năng trong việc tiếp cận các bài toán về số nguyên tố.
1.2. Mục đích của đề tài
 Mục đích của đề tài này là cung cấp một cách tiếp cận mới trong việc giải quyết các bài toán về số nguyên tố một cách tối ưu, đồng thời đưa ra các ví dụ để học sinh có thể làm quen, hình thành các kĩ năng trong việc tiếp cận và giải các bài toán có sử dụng sàng nguyên tố của Eratosthenes
1.3. Đối tượng nghiên cứu.
 Các bài toán liên quan đến số nguyên tố, được nghiên cứu ở nhiều tài liệu và các đề thi qua các năm được giải quyết bằng cách sử dụng sàng nguyên tố của Eratosthenes.
 Học sinh lớp 11 trường THPT 4 Thọ Xuân.
1.4. Phương pháp nghiên cứu
Sáng kiến kinh nghiệm đang trình bày của tôi dựa theo các luận cứ khoa học hướng đối tượng, vận dụng linh hoạt các phương pháp: quan sát, thuyết trình, vấn đáp, điều tra cơ bản, kiểm thử, phân tích kết quả thực nghiệm sư phạm,v.v phù hợp với bài học và môn học thuộc lĩnh vực cấu trúc dữ liệu.
 Tham khảo các bài tập tin học, bài tập Tin học nâng cao, tài liệu ôn luyện học sinh giỏi và một số đề thi học sinh giỏi môn Tin học.
 Nghiên cứu các tài liệu liên quan đến sàng nguyên tố của Eratosthenes và rút ra phương pháp để làm quen với bài tập dạng này.
 Hướng dẫn cho học sinh làm quen và hình thành kĩ năng để giải một số bài toán cụ thể.
 Kiểm tra, đánh giá kết quả của học sinh trong quá trình triển khai đề tài để từ đó có những điều chỉnh, bổ sung hợp lí
2. NỘI DUNG NGHIÊN CỨU
2.1. Cơ sở lý luận
Căn cứ vào mục tiêu của môn Tin học, là phải cung cấp những tri thức cơ bản, làm nền tảng để học sinh có thể tiếp tục đi sâu vào tìm hiểu và xây dựng khoa học Tin học hoặc tiếp thu những tri thức của các lĩnh vực kĩ thuật công nghệ tiên tiến, nhất là các lĩnh vực của công nghệ thông tin, đặc biệt là trong giai đoạn với nhiều thời cơ và không ít thách thức của cuộc cách mạng công nghiệp 4.0 hiện nay. Nó hội tụ nhiều công nghệ, trong đó cốt lõi là công nghệ thông tin. Công nghệ thông tin xuất hiện trong hầu khắp các lĩnh vực, như: kinh tế chia sẻ 4.0, dịch vụ thông minh, nông nghiệp thông minh 4.0, y tế thông minh 4.0, giáo dục thông minh 4.0, giao thông thông minh 4.0,[1]
2.2. Thực trạng
Năm đầu tiên tôi tham gia công tác bồi dưỡng học sinh giỏi, việc dạy đội tuyển của tôi chủ yếu dựa trên những kiến thức cơ bản của sách giáo khoa, chưa biết cách cải tiến để chương trình tối ưu hơn để chương trình chạy nhanh hơn và chủ yếu là định hướng cho học sinh tìm ra được thuật toán để chương trình cho ra được kết quả mà thôi. Do đó kết quả học sinh giỏi năm đó chưa được như mong muốn, có 2 em học sinh tham gia thi học sinh giỏi Tin của trường và không có em nào đạt giải. Bản thân các em và giáo viên không hiểu vì sao kết quả lại thấp như vậy vì khi đi thi về các em rất phấn khởi vì thấy mình làm bài tốt, thấy bài của mình vẫn cho kết quả đúng giống trong đề nhưng tại sao điểm lại thấp như vậy. Và cuối cùng tôi cũng đã hiểu ra rằng khi giải quyết các bài toán về số nguyên tố nói riêng và các bài tập lập trình pascal khác nói chung, học sinh và ngay cả giáo viên thường chỉ làm việc với các bộ input có dữ liệu nhỏ dễ nhìn thấy kết quả output và thường không xét đến trường hợp input đặc biệt hay các input có dữ liệu lớn. Dẫn đến bị mất điểm trong bài thi học sinh giỏi.
Vấn đề đặt ra, là làm thế nào để lấy được điểm với các bộ input có dữ liệu lớn. Muốn vậy cần phải lựa chọn và cài đặt được chương trình hiệu quả nhất..
2.3. Các biện pháp sử dụng để giải quyết vấn đề
2.3.1. Cơ sở lý thuyết
 a. Cơ sở lý thuyết
Số nguyên tố: Là số tự nhiên chỉ có hai ước số dương phân biệt là {\displaystyle 1}1 và chính nó. [2]
Hợp số: Là một số tự nhiên có thể biểu diễn thành tích của hai số tự nhiên khác nhỏ hơn nó. Một định nghĩa khác tương đương: hợp số là số chia hết cho các số khác ngoài 1 và chính nó. [3]
Sàng nguyên tố : Là thuật toán do Eratosthenes đưa ra để tìm các số nguyên tố. Nó có đặc điểm khác với thuật toán khác là kiểm tra các số nguyên tố theo kiểu sàng lọc, xét tất cả những số cần kiểm, những số nào không phải là số nguyên tố thì bỏ đi. Thuật toán thích hợp cho bài toán tìm tất cả các số nguyên tố trong khoảng [a, b] mà đặc biệt hiệu quả khi khoảng cách giữa a, b là rất lớn. Eratosthenes (tiếng Hy Lạp: Ερατοσθένης; 276 TCN – 194 TCN) là một nhà toán học, địa lý và thiên văn người Hy Lạp. [4]
b. Hình thức của sàng Eratosthenes
 Ban đầu, nhà toán học Eratosthenes sau khi tìm ra thuật toán, đã lấy lá cọ và ghi tất cả các số từ 2 cho đến 100. Ông đã chọc thủng các hợp số và giữ nguyên các số nguyên tố. Bảng số nguyên tố còn lại trông rất giống một cái sàng. Do đó, nó có tên là sàng Eratosthenes [4]
c. Giải thuật
Xét từ 2 đến N
Bắt đầu với i=2
Trong khi i< Trunc(sqrt(N)) thì: 
 + Xóa bội của i, khác i
 + Tìm tiếp i đầu tiên chưa xóa
Cuối cùng các điểm chưa bị xóa là số nguyên tố.[4]
Minh họa cho bảng N=100 như sau:
 Ban đầu Kết quả sau khi sàng nguyên tố
Minh họa thuật toán
Giá trị i
Xóa bội của i
Màu ô
2
4;6;8;10;12;14;16;18;20;22;24;26;28;30;32;34;36;38;40;42;44;46;48;50;52;54;56;58;60;62;64;66;68;70;72;74;76;78;80;82;84;86;88;90;92;94;96;98;100
3
9;15;21;27;45;51;57;63;69;75;87;93;99
5
25;35;55;65;85;95
7
49;77;91
11;13;17;19;23;29;31;37;41;43;47;53;59;61;67;71;73;79;83;89;97
Không có bội nào trong bảng trên
Vậy ta sàng được các số nguyên tố trong đoạn [1;100] là: 2; 3;5;7;11;13;17;19;23;29;31;37;41;43;47;53;59;61;67;71;73;79;83;89;97
d. Cài đặt
Cách 1
Const
        nmax=1000;
var
        SNT:array[0..nmax+1] of boolean;
procedure sangnt;
var     i,j:longint;
begin
        fillchar(snt,sizeof(snt),true);
        snt[1]:=false;
        i:=2;
        while i<=trunc(sqrt(nmax)) do
                begin
                        while snt[i]=false do
                                inc(i);
                        for j:=2 to nmax div i do
                                snt[i*j]:=false;
                        inc(i);
                end;
Cách 2
procedure sangnt;
begin 
 fillchar(kt, sizeof(kt), true);
 kt[1]:= false;
 for i:=2 to trunc(sqrt(maxn)) do
 if kt[i] then
 for j:= 2 to maxn div i do
 kt[i*j]:= false;
end;
2.3.2. Bài tập vận dụng
Bài 1: Viết chương trình in ra các số nguyên tố từ 2 đến N.[5]
Thuật toán: Dùng thuật toán sàng nguyên tố để tìm đánh dấu tất cả các số nguyên tố bé hơn hoặc bằng N. Rồi duyệt từ 1 đến N. Nếu là số nguyên tố thì in ra.
Chương trình
Program Bai1;
Const         n=1000;
Var         SNT:array[0..n+1] of boolean;
 procedure sangnt;
var     i,j:longint;
begin
        fillchar(snt,sizeof(snt),true);         snt[1]:=false;         i:=2;
        while i<=trunc(sqrt(n)) do
                begin
                        while snt[i]=false do   inc(i);
                        for j:=2 to n div i do
                                snt[i*j]:=false;      inc(i);
                end;
         for i:=1 to n do
                if snt[i]=true then
                        write(i,' ');
end;
 begin
        sangnt;
        readln;
end.
Bài 2. Số nguyên tố [6]
Cho dãy số gồm có N số nguyên dương a1, a2,..., aN và một số nguyên dương K.
Yêu cầu: Hãy cho biết số lượng các phần tử có giá trị nhỏ hơn K là số nguyên tố của dãy số trên.
Dữ liệu: Dòng đầu tiên là hai số N và K.
Dòng tiếp theo lần lượt là N số nguyên của dãy số.
Kết quả: Gồm duy nhất số M là số lượng các phần tử của dãy số thoả mãn yêu cầu đề bài.
Giới hạn: 0 < N < 108; 0 < K < 106, |ai| < 109 < "i = 1..N;
Ví dụ:
PRIME.INP
PRIME.OUT
7 8
1 2 3 8 7 6 11
3
Thuật toán: Dùng thuật toán sàng nguyên tố để tìm đánh dấu tất cả các số nguyên tố bé hơn 106. Rồi duyệt tất cả các phần tử của mảng, chỉ xét các phần tử có giá trị bé hơn K, nếu nó là số nguyên tố thì tăng kết quả lên.
Chương trình
Program bai2;
const maxn=round(1e6);
 var n,i,j,k,dem:longint; kt:array[1..maxn] of boolean; 
 a:array[1..100000000] of longint;
Begin
fillchar(kt,sizeof(kt),true);
kt[1]:=false;
for i:=2 to trunc(sqrt(maxn)) do
 if kt[i]=true then
 for j:=2 to maxn div i do
 kt[i*j]:=false;
readln(n,k); dem:=0;
For i:=1 to n do
begin
readln(a[i]);
if( kt[a[i]]=true) and (a[i]<k) then inc(dem);
end;
writeln('so luong',dem);
readln
end.
Bài 3. Tìm mật khẩu (Trích- Bài 2 đề thi học sinh giỏi tỉnh lớp 12 THPT. Năm học 2014-2015. Tỉnh Thanh Hóa) [6]
 Việc bảo vệ máy tính của mình để hạn chế người khác thâm nhập vào là một vấn đề đặt ra cho mọi người sử dụng máy tính. Để tăng tính an toàn trong lưu trữ Lan đã quyết định đặt mật khẩu truy cập máy tính của mình vào một xâu T với một quy ước sao cho khi cần cô ta có thể lấy lại được mật khẩu từ xâu T như sau:
Là một người yêu thích số học cô ta thường chọn mật khẩu P là một số nguyên tố và đem giấu vào trong một xâu ký tự T sao cho P chính là số nguyên tố có giá trị lớn nhất trong số các số nguyên tố được tạo từ các xâu con của T (xâu con của một xâu ký tự T là một chuỗi liên tiếp các ký tự trong T).
Ví dụ: xâu T= “Test1234#password5426” chứa mật khẩu là 23 vì T chứa các xâu con ứng với các số nguyên tố 2, 3, 23 và 5.
Yêu cầu: cho một xâu ký tự T có chiều dài không quá 500 ký tự. Tìm mật khẩu P đã dấu trong xâu T biết P có giá trị nhỏ hơn 105. Dữ liệu cho đảm bảo luôn có P.
Dữ liệu vào: vào từ file văn bản BAI2.INP gồm 1 dòng duy nhất là xâu T.
Kết quả: ghi ra file văn bản BAI2.OUT là số P tìm được.
Ví dụ:
BAI2.INP
BAI2.OUT
Test1234#password5426
23
Thuật toán: Vì bài toán luôn có đáp số và kết quả của bài toán luôn nhỏ hơn 105 nên ta dùng thuật toán sàng nguyên tố để tìm đánh dấu tất cả các số nguyên tố nhỏ hơn 105 rồi cho i chạy từ 105 -1 về 2, nếu i là số nguyên tố và i có trong xâu thì in ra i và kết thúc luôn chương trình. 
Chương trình
Program bai3;
const maxn= round(1e5);
var st: ansistring; st1: string; i,j: longint; kt: array[1..maxn] of boolean;
 f,g:text;
procedure sangnt;
begin
 fillchar(kt, sizeof(kt), true);
 kt[1]:= false;
 for i:=2 to trunc(sqrt(maxn)) do
 if kt[i] then
 for j:= 2 to maxn div i do
 kt[i*j]:= false;
end;
BEGIN
 assign(f, 'bai2.inp'); reset(f); assign(g, 'bai2.out'); rewrite(g);
 readln(f, st);
 sangnt;
 for i:= 100000-1 downto 2 do
 if kt[i] then
 begin
 str(i,st1);
 if pos(st1,st)0 then
 begin
 write(g, st1); halt;
 end;
 end;
 close(f);
 close(g);
 END.
Bài 4: Số nguyên tố lớn thứ nhì (Trích Bài 3 đề thi giáo viên dạy giỏi THPT cấp tỉnh năm 2017 – 2018. Tỉnh Thanh Hóa)
Hôm nay trời bỗng dưng mưa to, Bờm không thể đi học được, vì nhà Bờm quá xa trường. Nếu đi học Bờm sẽ bị ướt hết người nên Bờm quyết định lấy sách Tin học lớp 11 ra để tự học. Ngồi học được một lúc, Bờm nghĩ ra một bài toán để ngày mai lên lớp đố các bạn. Bài toán như sau: Cho một dãy số nguyên không âm A1, A2, A3,..., AN-1, AN. Hãy tìm giá trị của số nguyên tố lớn thứ nhì của tất cả các số nguyên tố được lấy từ dãy số trên. Để hiểu rõ hơn về số nguyên tố lớn thứ nhì thì Bờm lấy 2 ví dụ sau:
+ Ví dụ 1: Xét dãy số gồm 6 số sau: 11, 2, 2, 4, 5, 7. Thì số nguyên tố lớn thứ nhì là 7. Giải thích: dãy trên ta có các số nguyên tố là 2, 5, 7, 11; thì số nguyên tố lớn nhất là 11, số nguyên tố lớn thứ nhì là 7.
+ Ví dụ 2: Dãy số nguyên gồm 4 số sau: 1, 2, 2, 0. Thì dãy số này không có số nguyên tố thứ nhì. Giải thích: Vì không có số nguyên tố nào nhỏ hơn 2.
Yêucầu: Các bạn hãy thử giải bài toán trên của Bờm.
Dữ liệu vào:Từ file văn bản BAI3.INP gồm
- Dòng đầu tiên chứa một số nguyên dương N. (N ≤ 106)
- Dòng thứ hai gồm N số nguyên không âm A1, A2, A3,..., AN-1, AN. (Ai≤ 106, với mọi i=1,2, ...N)
Dữ liệu ra: Ghi ra file văn bản BAI3.OUT là một số nguyên là kết quả của bài toán. Nếu không có số nguyên tố lớn thứ nhì thì in ra số -1
Ví dụ
 BAI3.INP
BAI3.OUT
BAI3.INP
BAI3.OUT
6
11 2 2 4 5 7
7
4
1 2 2 0
-1
Thuật toán dùng thuật toán sàng nguyên tố để tìm đánh dấu tất cả các số nguyên tố nhỏ hơn 106 . Rồi duyệt các phần tử của mảng và sử dụng thuật toán lùa bò vào chuồng. 
Chương trình
Program bai4;
Const maxN= round(1e6);
Var a: array[0..maxn+1] of longint; f: array[0..maxn+1] of boolean;
 i,n: longint; tim: longint; h,g:text;
procedure sangnt;
var i,j: longint;
Begin
 for i:= 2 to maxn do f[i]:= true;
 f[0]:= false; f[1]:= false;
 for i:=2 to trunc(sqrt(maxn)) do
 if f[i] then
 for j:= 2 to maxn div i do
 f[i*j]:= false;
End;
BEGIN
 assign(h ,'bai3.inp'); reset(h);
 assign(g, 'bai3.out'); rewrite(g);
 readln(h,n); sangnt; tim:=-1;
 for i:=1 to n do
 begin read(h, a[i]);
 if f[a[i]] then
 if tim<a[i] then tim:= a[i];
 end;
 for i:= 1 to n do
 if tim = a[i] then f[a[i]]:= false; tim:= -1;
 for i:=1 to n do
 if f[a[i]] then
 if tim<a[i] then tim:= a[i];
 writeln(g, tim);
 close(h); close(g);
END.
Bài 5: Số siêu nguyên tố( Trích Kì thi chọn học sinh giỏi tỉnh lớp 12 THPT năm học 2012 – 2013 môn Tin học. Tỉnh Hải Dương) [7]
Số siêu nguyên tố là số nguyên tố mà khi xoá bỏ dần các chữ số bên phải của nó thì phần còn lại vẫn là số nguyên tố. Ví dụ: 2333 là số siêu nguyên tố vì 2333, 233, 23, 2 đều là các số nguyên tố.
Yêu cầu: Cho số nguyên dương M (M ≤ 30000). Hãy tìm số siêu nguyên tố gần với M nhất, tức là trị tuyệt đối của hiệu giữa số tìm được với M là nhỏ nhất)
Dữ liệu: Nhập vào từ bàn phím số nguyên dương M (không cần kiểm tra dữ liệu nhập)
Kết quả: Ghi ra màn hình các số nguyên tố gần M nhất, mỗi số một dòng theo thứ tự số nhỏ hơn ghi trước.
Ví dụ:
Input
Output
30
29
31
Thuật toán: dùng thuật toán sàng nguyên tố để tìm đánh dấu tất cả các số nguyên tố nhỏ hơn 30000 . Rồi xây dựng chương trình con kiểm tra một số có phải là số siêu nguyên tố hay không. Sau đó xét 2 trường hợp của số nguyên tố gần M nhất là số đứng trước và số đứng sau.
 Chương trình:
Program BAI5;
Var d: array[1..30000] of byte; M: longint; var a, b: longint;
Procedure sangNT;
Var i,j: longint;
Begin
 for i:=1 to 30000 do d[i]:=0;
 d[1]:=1; i:=1;
 while i*i<=30000 do
 begin
 repeat inc(i) until (i*i>30000) or (d[i]=0);
 if i*i<=30000 then
 begin
 j:=2;
 while i*j<=30000 do
 begin
 d[i*j]:=1; inc(j);
 end;
 end;
 end;
End;
Function sieunt(x: longint): boolean;
Begin
 repeat
 if d[x]=1 then
 begin
 sieunt:=false; exit;
 end;
 x:=x div 10;
 until x=0;
 sieunt:=true;
End;
BEGIN
 sangNT; read(M); a:=m;
 while (a>0) and (not sieunt(a)) do dec(a); b:=m;
 while (b<30001) and (not sieunt(b)) do inc(b);
 if a>0 then writeln(a);
 if (bm) and (b<30001) then writeln(b);
 readln
END.
Bài 6. Tìm số nguyên tố ( Trích Bài 2. Đề thi học sinh giỏi cấp tỉnh THPT môn Tin học năm 2017- 2018. Tỉnh Thanh Hóa.)
Tìm tất cả các số P lớn hơn M và nhỏ hơn N thỏa mãn các điều kiện sau:
+ Là số nguyên tố.
+ Tổng các chữ số của P phải chia hết cho k.
Dữ liệu vào: Từ tệp văn bản BAI2.INP: Gồm 3 số M, N, k( 1≤ M, N, k ≤106)
 ( các số cách nhau ít nhất một dấu cách).
Dữ liệu ra: Ghi ra tệp văn bản BAI2.OUT gồm duy nhất 1 số là số lượng các số thỏa mãn yêu cầu đầu bài.
Ví dụ:
BAI2.INP
BAI2.OUT
BAI2.INP
BAI2.OUT
2 35 2
6
1 10 11
0
Thuật toán: dùng thuật toán sàng nguyên tố để tìm đánh dấu tất cả các số nguyên tố < 106 . Rồi xây dựng hàm tính tổng các chữ số của một số. Rồi duyệt từ m+1 đến n-1. Giá trị nào thỏa mãn điều kiện thì tăng biến đếm lên 1 đơn vị.
Chương trình
Program bai6;
const maxn=round(1e6);
var m,n,k: longint; dem, i, j: longint;
 kt: array[1.. maxn+1] of boolean; f,g: text;
procedure sangnt;
var i,j: longint;
begin
 kt[1]:= false;
 for i:=1 to maxn do kt[i]:= true;
 for i:=2 to trunc(sqrt(maxn)) do
 if kt[i]=true then
 for j:= 2 to maxn div i do
 kt[i*j]:= false;
end;
function tong(p: longint): longint;
begin
 tong:=0;
 while p>0 do
 begin
 tong:= tong + (p mod 10);
 p:= p div 10;
 end;
end;
BEGIN
 assign(f, 'bai2.inp'); reset(f);
 assign(g, 'bai2.out'); rewrite(g);
 readln(f, m,n,k); sangnt; dem:=0;
 for i:= m+1 to n-1 do
 if (kt[i]=true) and (tong(i) mod k =0) then inc(dem);
 writeln(g,dem); close(f); close(g);
END.
Bài 7. Đề bài P134SUMF spoj PTIT [8]
 (nguồn https://kienthuc24h.com/ P134SUMF spoj PTIT /)
Tí và Tèo đang cùng nhau học về sàng nguyên tố Eratosthenes.
Thuật toán sàng nguyên tố để tìm các số nguyên tố từ 2 tới N như sau:
1. Viết tất cả các số nguyên từ 2 tới N theo đúng thứ tự.
2. Tìm số nguyên nhỏ nhất chưa bị gạch. Gọi số đó là P. P sẽ là số nguyên tố.
3. Gạch bỏ P và tất cả các bội của nó.
4. Nếu tất cả các số chưa bị gạch bỏ, quay lại bước 2.
Tí đố Tèo rằng, cho trước N và K, hãy tìm số thứ K sẽ bị gạch 
Input : Chứa 2 số nguyên N và K (2 ≤ K < N ≤ 1000).
Output: Hãy in ra số thứ K sẽ bị gạch bỏ.
Ví dụ:
Input
Output
Input
Output
Input
Output
7 3
6
15 12
7
10 7
9
Giải thích test 3: Các số lần lượt bị gạch bỏ sẽ là 2, 4, 6, 8, 10, 3, 9, 5, 7.
Do đó số thứ 7 sẽ là 9.
Chương trình:
Program bai7;
const fi='bai7.inp'; nmax=1000;
 type data=longint;
var f:text; x,M:data; A:array[1..nmax] of boolean;
procedure xuli;
var i,j,k:data;
begin
 for i:=1 to x do a[i]:=false;
 i:=2; k:=0;
 while i<=x do
 begin
 if not a[i] then
 begin
 for j:=1 to x div i do
 if not a[i*j] then
 begin
 inc(k);
 if k=m then
 begin
 writeln(i*j); exit;
 end;
 a[i*j]:=true;
 end;
 end; inc(i);
 end;
end;
 BEGIN
 assign(f,fi); reset(f);
 while not eof(f) do
 begin
 readln(f,x,m);
 xuli; end;
END.
Bài 8. Đề bài BCACM11D spoj [9]
( Nguồn https://kienthuc24h.com/bcacm11d-spoj-ptit-duong-nguyen-to/