Bồi dưỡng kĩ năng giải bài tập về số nguyên tố dành cho học sinh lớp 11 trường Trung học phổ thông Tĩnh Gia 2

A. PHẦN MỞ ĐẦU
I. Lí do chọn đề tài.
Hiện nay trong lí luận dạy học nói chung và lí luận dạy học môn tin học nói riêng đề cập khá nhiều phương pháp và kỹ thuật dạy học: phương pháp thảo luận, phương pháp đặt câu hỏi, phương pháp chia nhóm 
Các cách thiết kế bài giảng hiện nay nhằm mục đích áp dụng phương pháp hiện đại để bồi dưỡng cho học sinh năng lực ham muốn học hỏi, tư duy sáng tạo, năng lực tự giải quyết vấn đề, rèn luyện và phát triển năng lực tự học sáng tạo, nghiên cứu, nghĩ và làm việc một cách tự chủ Đồng thời để thích ứng với sự phát triển tư duy của học sinh trong xã hội mới và tiếp cận với các công nghệ tiên tiến trong xã hội, trên thế giới. Bên cạnh đó, trong các kỹ thuật dạy học mới, vai trò của người thầy có sự thay đổi là: “hướng dẫn học sinh biết tự mình tìm ra hướng giải quyết những vấn đề nảy sinh trong quá trình học tập, biết cách làm việc độc lập, làm việc tập thể. Thầy là người định hướng, là người cố vấn giúp học sinh tự đánh giá, cũng như giúp học sinh luôn đi đúng con đường tìm hiểu, lĩnh hội kiến thức”.
Xuất phát từ thực tiễn giảng dạy tại trường THPT Tĩnh Gia 2 tôi thấy rằng, để đạt hiệu quả cao trong mỗi phần học, tiết học cần có cách thiết kế bài giảng cho phù hợp với nội dung kiến thức; phương pháp, phương tiện dạy học phải phù hợp với từng đối tượng học sinh. Để qua mỗi phần học, tiết học thì học sinh thích thú với kiến thức mới, qua đó hiểu được kiến thức đã học trên lớp, đồng thời học sinh thấy được tầm quan trọng của vấn đề và việc ứng dụng của kiến thức trước hết để đáp ứng những yêu cầu của môn học, sau đó là việc ứng dụng của nó vào các công việc thực tiễn trong đời sống xã hội.
Trong thời đại thông tin bùng nổ ngày nay, việc lập được các chương trình tự hoạt động cho máy tính, máy gia dụng là cần thiết. Và để làm được việc đó cần có một quá trình nghiên cứu, học tập về ngôn ngữ lập trình lâu dài, qua đó nhà lập trình có thể chọn một ngôn ngữ lập trình thích hợp. Tuy nhiên mọi thứ điều có điểm khởi đầu của nó, với học sinh việc học Pascal là khởi đầu cho việc tiếp cận ngôn ngữ lập trình bậc cao, qua đó giúp các em hình dung được sự ra đời, cấu tạo, hoạt động cũng như lợi ích của các chương trình hoạt động trong máy tính, các máy tự độngQua đó giúp các em có thêm một định hướng, một niềm đam mê về tin học, về nghề nghiệp mà các em chọn sau này. Đồng thời Pascal là một ngôn ngữ có cấu trúc thể hiện trên 3 yếu tố: Cấu trúc về mặt dữ liệu, cấu trúc về mặt lệnh, cấu trúc về mặt chương trình.
Trong quá trình dạy đội tuyển học sinh giỏi tỉnh, tôi nhận thấy rằng trong chương trình phổ thông dạng bài toán về số nguyên tố xuất hiện với tần suất cao. Ngay từ lớp 10 khi tìm hiểu về thuật toán học sinh đã làm quen về thuật toán số nguyên tố. Tuy nhiên ở lớp 10 chúng ta chỉ mới tìm hiểu sơ bộ về số nguyên tố. Khi bồi dưỡng đội tuyển học sinh giỏi giáo viên và học sinh cần đi sâu vào chuyên đề này ở các dạng bài toán biến hóa khác nhau 
Xuất phát từ cơ sở trên tôi đã chọn Đề tài “Bồi dưỡng kĩ năng giải bài tập về số nguyên tố dành cho học sinh lớp 11 trường Trung học phổ thông Tĩnh Gia 2”
II. Mục đích đề tài
Từ thuật toán cơ bản trong SGK tin học 10 ở bài số 4: “Bài toán và thuật toán” phát triển sâu về chuyên đề “Bồi dưỡng kĩ năng giải bài tập về số nguyên tố dành cho học sinh lớp 11 trường Trung học phổ thông Tĩnh Gia 2” trong giảng dạy học sinh phổ thông và đặc biệt dùng trong bồi dưỡng học sinh giỏi nhằm hướng dẫn học sinh giải quyết các bài toán về dạng số nguyên tố.
III. Nhiệm vụ đề tài
Phát triển và đi sâu về chuyên đề số nguyên tố thông qua thuật toán cơ bản trong sách giáo khoa lớp 10 và 11 để giải quyết bài toán: Kiểm tra tính nguyên tố của số nguyên N.
IV. Đối tượng nghiên cứu.
Học sinh khối 11 và đặc biệt là học sinh tham gia bồi dưỡng học sinh giỏi trường và tỉnh tại trường THPT Tĩnh Gia 2 .	
V. Phương pháp nghiên cứu .
- Kết hợp thực tiễn giáo dục ở trường THPT Tĩnh Gia 2 .
- Có tham khảo các tài liệu về ngôn ngữ lập trình Pascal, một số đề thi HSG trường và tỉnh và tài liệu về sáng kiến kinh nghiệm.
B. NỘI DUNG 
I. Thực trạng vấn đề
Tôi là giáo viên thường được nhà trường phân công dạy lớp chọn và đứng đội tuyển thi học sinh giỏi tỉnh, trong quá trình giảng dạy một thực tế gặp phải khi giải quyết các bài toán lập trình trên ngôn ngữ pascal với những ví dụ cơ bản trong sách giáo khoa các em sẽ dễ giải quyết được. Tuy nhiên khi đưa ra các bài toán với độ phức tạp cao hơn thì học sinh sẽ khó giải quyết. Vấn đề đặt ra ở đây là từ bài toán toán cơ bản trong sách giáo khoa nếu chúng ta hướng dẫn cho học sinh giải quyết với nhiều cách giải khác nhau và trên cơ sở các cách giải đó để vận dụng giải quyết các bài toán phức tạp hơn . 
	Trải qua quá trình dạy học nhiều năm và bồi dưỡng học sinh giỏi tôi đã đúc rút được kinh nghiệm khi giải quyết các bài toán phức tạp cần chia nhỏ bài toán đó ra thành các mô đun, mỗi mô đun là 1 chương trình con giải quyết 1 việc nào đó, đồng thời biết phân luồng các dạng bài toán tương ứng với các mảng để học sinh dễ giải quyết.
II. Biện pháp thực hiện
	Để giải quyết vấn đề trên tôi thực hiện qua 2 bước chính:
Bước 1: giúp học sinh hiểu rõ nội dung chính về lí thuyết số nguyên tố làm kiến thức nền tảng để giải các dạng bài tập vận dụng.
Bước 2: giảng dạy giúp học sinh nhận biết, lập trình để giải quyết các dạng bài tập vận dụng.
	Sau đây tôi xin trình bày cách thực hiện các bước trên:
II.1. Nội dung chính về lí thuyết số nguyên tố
Trong tin học lớp 10 học sinh đã làm quen với một số thuật toán trong đó có thuật toán “ Kiểm tra tính nguyên tố của một số nguyên dương ”
Như vậy chúng ta nhận thấy rằng thuật toán về số nguyên tố là một trong những thuật toán thường gặp trong các bài toán. Nhất là khi bồi dưỡng học sinh giỏi thì chúng ta lại thấy bài toán số nguyên tố được vận dụng rất nhiều trong các bài toán khó. 
Ý tưởng: Ta nhớ lại định nghĩa: Một số nguyên dương N là số nguyên tố nếu nó có đúng 2 ước số khác nhau là 1 và chính nó. Từ định nghĩa đó ta suy ra
- Nếu N=1 thì N không là số nguyên tố
- Nếu 1<N<4 thì N là số nguyên tố
- Nếu N 4 và không có ước số trong phạm vi từ 2 đến phần nguyên căn bậc 2 của N thì N là số nguyên tố.
Chứng minh tại sao N không có các ước từ 2 đến phần nguyên căn bậc 2 của N thì N là số nguyên tố.
Chỉ cần chứng minh 
 Vì nếu N>1 không phải là số nguyên tố, ta luôn có thể tách n=k1 x k2 mà
 2 Vì nên 
Do đó, việc kiểm tra với k từ 2 đến n-1 là không cần thiết mà chỉ cần kiểm tra có tồn tại ước từ 2 đến phần nguyên căn bậc 2 của N. Từ đó ta có thuật toán sau:
Thuật toán 
 a, Cách liệt kê
Bước 1: Nhập số nguyên dương N;
Bước 2: Nếu N = 1 thì thông báo N không nguyên tố rồi kết thúc;
Bước 3: Nếu N < 4 thì thông báo N là nguyên tố rồi kết thúc;
Bước 4: i ¬ 2;
Bước 5: Nếu i > []thì thông báo N là nguyên tố rồi kết thúc;
Bước 6: Nếu N chia hết cho i thì thông báo N không nguyên tố rồi kết thúc;
Bước 7: i ¬ i + 1 rồi quay lại bước 5.
Ghi chú	
BiÕn i nhËn gi¸ trÞ nguyªn thay ®æi trong ph¹m vi tõ 2 ®Õn + 1 vµ dïng ®Ó kiÓm tra N cã chia hÕt cho i hay kh«ng
b, Sơ đồ khối
§óng
NhËp N
N = 1 ? 
Th«ng b¸o N lµ sè nguyªn tè råi kÕt thóc
i ¬ 2 
i>?
i ¬ i + 1 
N chia hÕt cho i ? 
N < 4 ?
Th«ng b¸o N kh«ng lµ sè NT råi kÕt thóc
§óng
Sai
Sai
§óng
Sai
§óng
Sai
Mô phỏng ví dụ để thực hiện thuật toán
Với N = 29 ()
Với N = 45 ()
I
2
3
4
5
6
I
2
3
N/i
29/2
29/3
29/4
29/5
N/i
45/2
45/3
Không
Không
Không
Không
không
Chia hết
a) 29 là số nguyên tố
b) 45 không là số nguyên tố
Trên cơ sở thuật toán tiến hành cài đặt thuật toán như sau:
Viết mô đun chương trình con
Function nt(n: longint): boolean;
Var k, M: integer;
 Begin
 	If N=1 then begin nt:= false; exit end;
 	If (N=2) or (N=3) then begin nt:=true; exit end;
 	M:=trunc(sqrt(N));
For k:= 2 to m do
If ( N mod k =0) then begin nt:=false; exit ; end;
 	nt:=true;
end;
 Hàm nt(N) trên tiến hành kiểm tra lần lượt từng số nguyên k trong đoạn từ 2 đến phần nguyên căn bậc 2 của N. 
Để cải tiến cần giảm thiểu số các số cần kiểm tra. Thay vì kiểm tra các số k ta sẽ chỉ kiểm tra các số k có tính chất giống tính chất của số nguyên tố.
Tính chất số nguyên tố:
Trừ số 2 và số 3 các số nguyên tố có dạng 6k1 ( vì các số có dạng 6k2 thì chia hết cho 2, 6k 3 thì chia hết cho 3)
Ta có mô đun chương trình con như sau
function nt(n:longint):boolean;
var k,m,i:longint;
begin
 	if (n=2) or (n=3) then begin nt:=true; exit; end;
 	if( (n=1) or (n mod 2=0) or (n mod 3 =0)then begin nt:=false; exit; end;
 	k:=-1;
 	m:=trunc(sqrt(n));
 	repeat
 	 inc(k,6); if (n mod k =0) or (n mod (k+2) = 0) then break;
 	until k>m;
 	if k>m then nt:=true else nt:=false;
end;
Áp dụng chương trình con để giải quyết các dạng bài toán về số nguyên tố
II.2. Một số dạng bài toán về số nguyên tố
Dạng 1: Liệt kê các số nguyên tố trong đoạn từ [2,N] .
Cụ thể:
Bài toán 1: Viết chương trình liệt kê các số nguyên tố trong đoạn từ [2,N]
Dữ liệu : Vào từ tệp nguyento.inp số nguyên N
Kết quả: Ghi ra tệp nguyento.out chứa các số nguyên tố, mỗi số cách nhau 1 kí tự cách. Ghi trên cùng 1 dòng.
Ý tưởng bài toán này như sau:
-Xây dựng hàm kiểm tra số tính nguyên tố số nguyên N .
- Xây dựng chương trình con liệt kê các số nguyên tố trong đoạn từ 2 đến N. Bằng cách sử dụng lời gọi hàm nt(i). Nếu hàm nt(i) (trong đó i nhận giá trị từ 2 đến N) nếu hàm nhận giá trị đúng thì giá trị i được ghi vào tệp write(f2, i,’ ‘).
Thông qua đoạn chương trình:
For i:=2 to N do 
If nt(i) then write(f2, i, ‘ ‘);
Chương trình hoàn thiện như sau 
const fi='nguyento.inp';
 fo='nguyento.out';
var n,m, i:longint;
 f1,f2:text;
procedure doctep;
begin
assign(f1,fi);
reset(f1);
read(f1,n);
assign(f2,fo);
rewrite(f2);
end;
function nt(n:longint):boolean;
var k, M:longint;
begin
if n=1 then begin nt:=false; exit ; end;
if (n=2) or (n=3) then begin nt:=true; exit; end;
M:=trunc(sqrt(n));
for k:=2 to M do
if n mod k=0 then begin nt:=false; exit; end;
nt:=true;
end;
procedure xulytep;
begin
for i:=2 to n do if nt(i) then write(f2,i,' ');
end;
procedure dongtep;
begin
close(f1);
close(f2);
end;
begin
doctep;
xulytep;
dongtep;
end.
 Đây là một trong những dạng bài tập về số nguyên tố đơn thuần tuy nhiên khi dữ liệu lớn, ta cần giải quyết bài toán này với mô đun chương trình con về số nguyên tố ở thuật toán thứ 2 là dựa vào tính chất của số nguyên tố.
 Cũng là ý tưởng như trên nhưng ở đây xây dựng hàm nguyên tô nt(N) dựa vào tính chất của nó thì chương trình sẽ chạy nhanh hơn rất nhiều.
Ta có chương trình hoàn thiện như sau: 
const fi='nguyento.inp';
 fo='nguyento.out';
var n,m, i:longint;
 f1,f2:text;
procedure doctep;
begin
assign(f1,fi);
reset(f1);
read(f1,n);
assign(f2,fo);
rewrite(f2);
end;
function nt(n:longint):boolean;
var k, M:longint;
begin
if (n=2) or (n=3) then begin nt:=true; exit; end;
if (n=1) or (n mod 2=0) or (n mod 3=0) then begin nt:=false; exit ; end;
M:=trunc(sqrt(n));
K:=-1;
Repeat
 Inc(k,6);
 if (n mod k=0) or (n mod (k+2)=0) then begin break;
until k>M;
if k>m then nt:=true else nt:=false;
end;
procedure xulytep;
begin
for i:=2 to n do if nt(i) then write(f2,i,' ');
end;
procedure dongtep;
begin
close(f1);
close(f2);
end;
begin
doctep;
xulytep;
dongtep;
end.
Dạng thứ 2: Số siêu nguyên tố.
Số siêu nguyên tố là số nguyên tố mà khi bỏ một số tùy ý 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ụ: 37337 là một số siêu nguyên tố có 5 chữ số vì 3733,373,37,3 cũng là các số nguyên tố.
Bài toán 2:Hãy viết chương trình đọc dữ liệu vào là một số nguyên N (0<N<10) và đưa ra kết quả các số siêu nguyên tố có N chữ số và số lượng của chúng. 
 Vào file SNT.INP chứa duy nhất chỉ số nguyên N
Kết quả: Ghi ra file SNT.OUT 
ghi các số siêu nguyên tố
Số lượng các số siêu nguyên tố.
 SNT.INP
SNT.OUT
5
23333 23339 23399 23993 29399 31193 31379 
37337 37339 37397 59393 59399 71933 73331 73939
Co 15 so sieu nguyen to co 5 chu so
Ý tưởng của bài toán như sau:
- Xây dựng hàm kiểm tra so nguyên N có là số nguyên tố hay không
- Xây dưng hàm kiểm tra số i có phải là số siêu nguyên tố hay không 
Ý tưởng như sau:
Lại một lần nữa sử dụng lời gọi hàm nt(i) trong chương trình con
Nếu nt(i):=false thì SNT:=False ;
Nếu nt(i)=true thì tiến hành giảm giá trị của i bằng cách chia nó cho 10 (i:= i div 10) và lại quay lại kiểm tra i cho đến khi i giảm xuống i=0 then snt:=true;
Chương trình con như sau:
function snt(i:longint):boolean;
begin
snt:=false;
repeat
if nt(i)=false then exit
else
i:= i div 10;
until i=0;
snt:=true;
end;
- Xây dựng chương trình con thủ tục đưa ra các số siêu nguyên tố và ghi vào tệp đồng thời ứng với mỗi số là siêu nguyên tố thì đếm . 
- Ý Tưởng
 + Trước hết tìm giá trị đầu và giá trị cuối của số có n chữ số 
Gtd:=1; gtc:=1;
For i:=1 to n-1 do gtd:=gtd*10;
Gtc:=(gtd*10)-1;
 + Sau khi tìm được giá trị đầu và giá trị cuối thì tiến hành kiểm tra các số có n chữ số trong khoảng từ GTD đến GTC. Nếu là số siêu nguyên tố thì ghi vào tệp và đồng thời đếm
Thể hiện qua đoạn lệnh sau:
For i:=gtd to gtc do 
If snt(i) then begin write(f2, i,’ ‘); inc(dem); end;
Thể hiện chương trình con sau
procedure xulytep;
var 	gtd,gtc:longint;
dem:integer;
begin
gtd:=1;
gtc:=1;
dem:=0;
for i:=1 to n-1 do gtd:=gtd*10;
gtc:=gtd*10;
dec(gtc);
for i:=gtd to gtc do
if snt(i) then
begin
 write(f2,i,' ');
 inc(dem);
end;
writeln(f2);
write(f2, 'co ',dem,'so sieu nguyen to');
end;
Chương trình hoàn thiện cho bài toán :
const fi='nguyento.inp';
 fo='nguyento.out';
var 	n,m, i:longint;
 	f1,f2:text;
procedure doctep;
begin
assign(f1,fi);
reset(f1);
read(f1,n);
assign(f2,fo);
rewrite(f2);
end;
function nt(n:longint):boolean;
var k,m,i:longint;
begin
if (n=2) or (n=3) then begin nt:=true; exit; end;
if( (n=1)or (n mod 2=0)or (n mod 3 =0) )then begin nt:=false; exit; end;
k:=-1;
m:=trunc(sqrt(n));
repeat
 inc(k,6);
if (n mod k =0) or (n mod (k+2) = 0) then break;
until k>m;
 if k>m then nt:=true
 else nt:=false;
end;
function snt(i:longint):boolean;
begin
snt:=false;
repeat
if nt(i)=false then exit
else
i:= i div 10;
until i=0;
 snt:=true;
end;
procedure xulytep;
var	gtd,gtc:longint;
dem:integer;
begin
gtd:=1; gtc:=1; dem:=0;
for i:=1 to n-1 do gtd:=gtd*10;
gtc:=gtd*10;
dec(gtc);
for i:=gtd to gtc do
if snt(i) then
begin
 write(f2,i,' ');
 inc(dem);
end;
writeln(f2);
write(f2, 'co ',dem,'so sieu nguyen to');
end;
procedure dongtep;
begin
close(f1);
close(f2);
end;
begin
doctep;
xulytep;
dongtep;
end.
Dạng 3: Tính chất của dãy số
Bài toán 3: Dãy số đặc biệt
Dãy số A1,A2,...,An được gọi là dãy số đặc biệt nếu nó thỏa mãn các điều kiện sau
Là dãy số giảm dần
Với mỗi A thì A’ hoặc là số nguyên tố hoặc là ước của một trong các số từ A1 đến Ai-1
Em hãy tìm dãy số đặc biệt dài nhất bắt đầu từ N.
Dữ liệu vào: Từ File văn bản DAYSO.INP là một số nguyên dương N (N<10000)
Kết quả: Ghi ra File văn bản DAYSO.OUT là dãy số tìm được các số cách nhau bởi dấu cách.
DAYSO.INP
DAYSO.OUT
12
12 11 7 6 5 4 3 2 1
Ý tưởng bài toán:
 - Xây dựng một hàm kiểm tra tính nguyên tố 
 - Tìm các số thỏa mãn điều kiện là số nguyên tố hoặc là ước của N ghi vào tệp
procedure ghitep;
begin
 write(f2,n,' ');
 for j:=n-1 downto 1 do
 if (N mod j =0) or (nt(j)) then write(f2,j,' ');
end;
Như vậy với dạng toán này chúng ta nghĩ ngay đến hàm nguyên tố
 Chương trình hoàn thiện như sau:
const fi='DAYSO.INP';
 fo='DAYSO.OUT';
var f1,f2:text;
 a:array[1..10000] of longint;
 n,i,j:longint;
procedure doctep;
begin
 assign(f1,fi);
 reset(f1);
 while not eof(f1) do
 read(f1,n);
 assign(f2,fo);
 rewrite(f2);
end;
function nt(n:longint):boolean;
var k,m,i:longint;
begin
if (n=2) or (n=3) then begin nt:=true; exit; end;
if( (n=1)or (n mod 2=0)or (n mod 3 =0) )then begin nt:=false; exit; end;
k:=-1;
m:=trunc(sqrt(n));
repeat
 inc(k,6);
if (n mod k =0) or (n mod (k+2) = 0) then break;
until k>m;
 if k>m then nt:=true
 else nt:=false;
end;
procedure ghitep;
begin
 write(f2,n,' ');
 for j:=n-1 downto 1 do
 if (N mod j =0) or (nt(j)) then write(f2,j,' ');
end;
procedure dongtep;
begin
close(f1);
close(f2);
end;
begin
doctep;
ghitep;
dongtep;
end.
Bài toán 4: Dãy con tăng nguyên tố
Cho 1 dãy N số nguyên dương. Dãy con tăng nguyên tố M phần tử là 1 dãy số có dạng:
Ai1	Ai2	Ai3		Aim
Và thỏa điều kiện
1 <= i1 < i2 < i3 <  < im <= n
Ai1 <= Ai2 <= Ai3 <=  <= Aim
Ai là số nguyên tố (số nguyên tố là số chỉ có đúng 2 ước số là 1 và chính nó)
Hãy tìm độ dài của dãy con tăng nguyên tố dài nhất
Dữ liệu nhập: vào từ file DAYCON.INP với định dạng như sau:
- Dòng đầu tiên là số N <= 1000 (tức là số phần tử của dãy số ban đầu)
- Các dòng tiếp theo chứa N số nguyên là giá trị các phần tử của dãy số (0<=A[i]<=100000)
Dữ liệu xuất: xuất ra file DAYCON.OUT 
- Số đầu tiên là số M tức phần tử của dãy con tăng nguyên tố dài nhất
- M dòng sau ghi ra giá trị các phần tử của dãy con tăng dài nhất
DAYCON.inp
DAYCON.out
13
3 13 6 8 7 
12 9 5 
11 6 3 13 
15
4
3 7 11 13
Ý tưởng bài toán như sau:
- Xây dựng hàm nguyên tố
- Xây dựng chương trình con tìm ra các phần tử của dãy là số nguyên tố đồng thời các số thỏa mãn điều kiện giá trị sau lơn hơn giá trị trước. Vì vậy cần tìm được 1 dãy đơn điệu tăng lớn nhất.
program day_con_tang_nguyen_to;
const fi='daycon.inp';
 fo='daycon.out';
var f1,f2:text;
 i,n,j,t,csmax:integer;
 a,b,c,d:array[0..1001] of integer;
procedure nhapdulieu;
begin
assign(f1,fi); assign(f2,fo);
reset(f1); rewrite(f2);
readln(f1,n);
for i:=1 to n do read(f1,a[i]);
end;
function nt(n:longint):boolean;
var k,m,i:longint;
begin
if (n=2) or (n=3) then begin nt:=true; exit; end;
if( (n=1)or (n mod 2=0)or (n mod 3 =0) )then begin nt:=false; exit; end;
k:=-1;
m:=trunc(sqrt(n));
repeat
 	inc(k,6);
if (n mod k =0) or (n mod (k+2) = 0) then break;
until k>m;
 if k>m then nt:=true
 else nt:=false;
end;
procedure dongtep;
begin
close(f1); close(f2);
end;
procedure qhd;
begin
b[csmax]:=1;
for i:=j downto 0 do 
begin
csmax:=j+1;
 for t:=i+1 to j+1 do
 if (a[t]>a[i])and(b[t]>b[csmax]) then csmax:=t;
 b[i]:=b[csmax]+1; c[i]:=csmax;
end;
write(f2,b[0]-2,' '); i:=c[0];
while in+1 do 
begin
write(f2,a[i],' '); i:=c[i];
end;
end;
procedure thaotac;
begin
j:=0;
for i:=1 to n do if kt(a[i]) then begin inc(j); d[j]:=a[i]; end;
a[0]:=-32768; a[n+1]:=32767;
qhd;
end;
begin
nhapdulieu;
thaotac;
dongtep;
end.
Dạng 4: Phân tích 1 số ra tích hoặc tổng các số nguyên tố.
Bài toán 5: Cho trước số tự nhiên N lập trình phân tích n thành tích các thừa số nguyên tố.
Dữ liệu: Vào File PTNT.INP chỉ chứa một số duy nhất N
Kết quả: Ghi vào file PTNT.OUT tích các thừa số nguyên tố 
PTNT.INP
PTNT.OUT
18
2*3*3
Với dạng bài toán này ta có thể sử dụng hàm nguyên tố hoặc không sử dụng hàm nguyên tố mà chỉ sử dụng tính chất của số nguyên tố 
- Ý tưởng bài toán: 
 Xây dựng mô đun chương trình con phân tích một số N ra thừa số nguyên tố bằng cách khởi gán giá trị ban đâu i:=2; tiến hành kiểm tra trong khi (n mod i =0) thì thay đổi giá trị n:= n div i, đồng thời ghi giá trị i vào tệp.
Lưu ý khi ghi giá trị i vào tệp cần kiểm tra giá trị n. Nếu n=1 thì write(f2,i) ngược lại ghi write(f2,i,'*'). Mô đun chương trình như sau
procedure thua_sont(n:integer);
var m:integer;
begin
 m:=trunc(sqrt(n));
 	i:=2;
while i<=m do
begin
while n mod i=0 do
 	begin
 	n:=n div i;
 	if n=1 then write(f2,i) else write(f2,i,'*');
 	end;
i:=i+1;
end;
end;
Chương trình hoàn thiện 
const fi='PTNT.INP';
 fo='PTNT.OUT';
var 	f1,f2:text;
 	i,j,n:integer;
procedure doc_tep;
begin
 assign(f1,fi);
 assign(f2,fo);
 reset (f1);
 rewrite(f2);
 readln(f1,n);
end;
procedure thua_sont(n:integer);
var	 m:integer;
begin
 m:=trunc(sqrt(n));
 	i:=2;
 while i<=m do
begin
while n mod i=0 do
 begin
 n:=n div i;
 if n=1 then