SKKN Một số kinh nghiệm khi vận dụng thuật toán kiểm tra tính nguyên tố của một số nguyên dương trong công tác bồi dưỡng học sinh giỏi môn Tin học trường THPT 4 Thọ Xuân

 1. MỞ ĐẦU
1.1. Lí do chọn đề tài
- Trong các trường học hiện nay, việc phát triển bồi dưỡng học sinh giỏi góp phần đào tạo nhân lực, bồi dưỡng nhân tài cho địa phương, đất nước luôn được xem là nhiệm vụ cần thiết và quan trọng. Nhiều năm qua trong công tác bồi dưỡng học sinh giỏi của trường, tôi luôn cố gắng tìm hiểu nội dung từ cơ bản đến nâng cao, tìm ra giải pháp tối ưu để công tác bồi dưỡng học sinh giỏi có hiệu quả nhất. 
- Trong các kì thi chọn HSG Tin học cấp Tỉnh và Quốc gia các bài toán về số nguyên tố là một mảng kiến thức quan trọng trong cấu trúc của đề thi và để giải được các bài toán đó luôn là trăn trở của mỗi học sinh cũng như các thầy cô giáo trực tiếp giảng dạy ở các trường THPT, các trường THPT Chuyên cả nước.
- Nhận thấy thuật toán kiểm tra tính nguyên tố của một số nguyên dương là thuật toán căn bản khi làm việc với những bài toán về số nguyên tố trong các đề thi học sinh giỏi Tỉnh, do đó bằng tất cả sự nỗ lực của bản thân, qua quá trình tìm tòi, trao đổi và thảo luận với các đồng nghiệp, tôi mạnh dạn xây dựng đề tài sáng kiến kinh nghiệm: "Một số kinh nghiệm khi vận dụng thuật toán kiểm tra tính nguyên tố của một số nguyên dương trong công tác bồi dưỡng học sinh giỏi môn Tin học trường THPT 4 Thọ Xuân" nhằm nâng cao chất lượng ôn luyện góp một phần nhỏ vào công tác bồi dưỡng chung của nhà trường, để đội ngũ học sinh giỏi của trường ngày càng đạt kết quả cao.
1.2. Mục đích nghiên cứu
- Thông qua thuật toán kiểm tra tính nguyên tố của một số nguyên dương và cách vận dụng nó vào giải các bài toán Tin học từ cơ bản đến nâng cao nhằm giúp học sinh trong đội tuyển rèn luyện kĩ năng lập trình, phát triển năng lực tư duy sáng tạo, hình thành kĩ năng nhận dạng và phân tích bài toán, qua đó nâng cao chất lượng bồi dưỡng đội tuyển HSG môn Tin học trong trường THPT 4 Thọ Xuân. 
1.3. Đối tượng nghiên cứu
Thuật toán kiểm tra tính nguyên tố bằng phương pháp thử chia.
Thuật toán sàng nguyên tố Eratosthene.
Các bài tập vận dụng.
Các em học sinh trong đội tuyển HSG Tin học.
1.4. Phương pháp nghiên cứu
Phương pháp quan sát sư phạm.
Phương pháp thống kê, thu thập, tổng hợp, báo cáo.
Phương pháp trải nghiệm thực tế.
2. NỘI DUNG
2.1. Cơ sở lý luận
- Giáo dục thế hệ trẻ là nhiệm vụ mà tất cả các quốc gia đều coi là chiến lược của dân tộc mình, mục đích nhằm nâng cao chất lượng dạy và học, xây dựng thế hệ học sinh trở thành những con người mới phát triển toàn diện, có đầy đủ phẩm chất đạo đức, năng lực, trí tuệ để đáp ứng với yêu cầu thực tế hiện nay.
- Đối với ngành giáo dục và đào tạo việc nâng cao chất lượng dạy và học luôn là mục tiêu trọng tâm, trong đó bồi dưỡng HSG là nhiệm vụ mũi nhọn. Để thực hiện được mục tiêu đó, trước hết chúng ta phải biết áp dụng phương pháp dạy học hiện đại kết hợp với những phương pháp dạy học truyền thống để bồi dưỡng cho học sinh năng lực tư duy sáng tạo, năng lực giải quyết vấn đề, rèn luyện thành nề nếp tư duy sáng tạo của người học, từng bước áp dụng các phương pháp tiên tiến, phương tiện hiện đại vào quá trình dạy học, tăng cường và dành thời gian tự học, tự nghiên cứu cho học sinh. Đồng thời bản thân mỗi giáo viên cũng phải tự tìm ra những phương pháp mới, khắc phục lối truyền thụ một chiều, phát huy tính tích cực, tự giác, chủ động, sáng tạo của học sinh trong các môn học nói chung, môn Tin học nói riêng.
- Qua quá trình nghiên cứu và rút kinh nghiệm từ bản thân, đồng nghiệp, tôi thấy thuật toán kiểm tra tính nguyên tố của một số nguyên dương là một kiến thức quan trọng và dạng toán vận dụng nó cũng rất đa dạng đòi hỏi học sinh phải có kiến thức vững chắc, nắm được trình tự các bước thực hiện, quy tắc vận dụng và khả năng tư duy, liên kết các kiến thức lại để giải bài toán một cách hiệu quả nhất. Tuy nhiên, phần nhiều học sinh còn bỡ ngỡ, thiếu các kĩ năng cơ bản, khả năng tư duy, tự nghiên cứu đặc biệt là tự học nên các em gặp nhiều khó khăn khi vận dụng thuật toán kiểm tra tính nguyên tố của một số nguyên dương để giải các bài toán. Chính vì thế, việc giúp cho học sinh giải được dạng toán này là một nhiệm vụ rất khó khăn đối với giáo viên. 
- Đối với công tác bồi dưỡng HSG môn Tin học trong nhà trường, tôi luôn luôn tâm huyết, dành nhiều thời gian nghiên cứu, tìm tòi, trau dồi để có nguồn kiến thức vững vàng, vận dụng linh hoạt, sáng tạo các phương pháp giảng dạy để việc bồi dưỡng đạt kết qủa tốt nhất. 
2.2. Thực trạng vấn đề trước khi áp dụng sáng kiến kinh nghiệm
2.2.1. Về phía giáo viên
Giáo viên đứng đội tuyển chưa có nhiều kinh nghiệm trong công tác bồi dưỡng nên còn gặp khá nhiều khó khăn trong công tác ôn luyện.
Được sự hỗ trợ, giúp đỡ của các thành viên trong tổ, trong trường. 
Nhà trường trang bị phòng máy vi tính và có lắp đặt mạng phục vụ nhu cầu tìm kiếm thông tin từ nhiều nguồn tạo điều kiện thuận lợi bước đầu cho giáo viên và học sinh trong quá trình ôn luyện.
Đảng, Nhà nước, Sở GD - ĐT, BGH nhà trường luôn quan tâm chú trọng đến chất lượng dạy và học, đặc biệt là đội ngũ học sinh giỏi.
2.2.2. Về phía học sinh
Học sinh đã được tiếp cận một thuật toán kiểm tra tính nguyên tố trong Bài 4 - SGK Tin học 10 và vận dụng vào giải quyết một số bài toán cơ bản. Xong với những bài toán khó hơn được dùng trong các kì thi học sinh giỏi Tỉnh ngoài khả năng vận dụng thuật toán kiểm tra tính nguyên tố cơ bản trong sách giáo khoa đòi hỏi các em phải biết vận dụng những thuật toán kiểm tra tính nguyên tố khác phù hợp hơn để giải quyết bài toán đạt hiệu quả tốt nhất. Tuy nhiên, các em còn gặp nhiều khó khăn, bế tắc, nhiều khi chưa tìm được thuật toán phù hợp, tối ưu, chưa tính đến thời gian chạy chương trình. 
- Do bước đầu tiếp cận việc lập trình nên kĩ năng còn nhiều hạn chế.
Trường THPT 4 Thọ Xuân với điểm trường đóng trên địa bàn xã điều kiện học tập của học sinh còn nhiều thiếu thốn, trình độ học vấn của các em còn thấp, đầu vào thấp do đó chất lượng mũi nhọn chưa cao ảnh hưởng không nhỏ đến chất lượng đội tuyển.
2.3. Giải pháp tổ chức thực hiện
Từ những khó khăn cơ bản của học sinh cũng như những yếu tố khách quan khác, tôi đã cố gắng tìm ra những giải pháp khắc phục nhằm đạt được hiệu quả cao trong công tác bồi dưỡng học sinh giỏi Tin học tại trường THPT 4 Thọ Xuân. Nắm bắt được tình hình xây dựng thuật toán cũng như khả năng vận dụng thuật toán, kĩ năng nhận dạng bài toán để đưa ra cách giải quyết của học sinh còn nhiều hạn chế, vậy nên ngoài việc cung cấp nguồn kiến thức đến các em tôi thường xuyên dành thời gian hướng dẫn, sửa chữa chỗ sai cho các em, tiếp thu, lắng nghe ý kiến từ các em. Thường xuyên cho các em làm những bài kiểm tra nhỏ để nắm bắt khả năng tiếp thu và vận dụng thuật toán của các em trong các bài toán. Tôi yêu cầu học sinh phải tự giác, tích cực, chủ động, có trách nhiệm với bản thân và tập thể, phải rèn luyện kĩ năng đọc và phân tích bài toán, kĩ năng lập trình máy tính, liên hệ và vận dụng linh hoạt thuật toán trong từng bài toán. 
Trong phạm vi đề tài này, tôi cung cấp đến các em nguồn kiến thức và một số kĩ năng thông qua các nội dung sau:
2.3.1 Khái niệm số nguyên tố và cách nhận biết
- Số nguyên tố là số tự nhiên lớn hơn 1 và chỉ có 2 ước số là 1 và chính nó. 
- Số tự nhiên có 2 ước số lớn hơn 1 thì không phải là số nguyên tố.
- Nếu số tự nhiên A>1 và không chia hết cho mọi số nguyên tố p mà p2<A thì A là số nguyên tố.
- Các số 0 và 1 không phải là số nguyên tố. 
- Mọi số nguyên tố lớn hơn 3 chia 6 dư 1 hoặc 5. 
- Bảng các số nguyên tố nhỏ hơn 100:
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
2.3.2. Xây dựng thuật toán của bài toán kiểm tra tính nguyên tố của một số nguyên dương N
Input: N là một số nguyên dương.
Output: "N là số nguyên tố" hay "N không là số nguyên tố".
2.3.2.1. Dùng phương pháp thử chia
Đây là phương pháp đã được vận dụng để xây dựng thuật toán của bài toán kiểm tra tính nguyên tố trong mục 3 - Trang 36 - SGK Tin học 10. 
Ý tưởng và thuật toán như sau:
Nếu N là 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 hai của N thì N là số nguyên tố; 
*Thuật toán 1: Cách liệt kê:
B1. Nhập số nguyên dương N;
B2. Nếu N = 1 thì thông báo N không nguyên tố rồi kết thúc;
B3. Nếu N< 4 thì thông báo N là nguyên tố rồi kết thúc;
B4. i <-- 2;
B5. Nếu i> [√N] thì thông báo N là nguyên tố rồi kết thúc;
B6. 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; 
B7. i <-- i + 1 rồi quay lại B5;
Trong các bài toán thi học sinh giỏi Tin học Tỉnh, dữ liệu xử lí thường khá lớn( ≤109), do vậy để đảm bảo một thuật toán cho ra một kết quả đúng trong thời gian có thể chấp nhận được thì khi xây dựng thuật toán luôn hướng tới mục đích tối ưu để có thuật toán hiệu quả nhất. 
* Cải tiến thuật toán:
Với thuật toán trên ta có một số nhận xét sau:
Tính [√n] và đưa ra trước vòng lặp kiểm tra n có chia hết cho i hay không.
Thuật toán được xây dựng trên phương pháp thử chia, do vậy ta chỉ cần giảm số giá trị của i cần kiểm tra là sẽ dẫn tới một thuật toán hiệu quả hơn.
Theo dấu hiệu nhận biết về số nguyên tố thì để kiểm tra n có phải là số nguyên tố hay không ta chỉ cần kiểm tra xem n có chia hết cho 1 trong các số nguyên tố i trong khoảng [2, [√n]]. 
Dựa vào kiến thức toán nâng cao về số nguyên tố thì ta có thể chứng minh mọi số nguyên tố lớn hơn 3 chia 6 dư 1 hoặc 5. 
Phân tích: Khi x = 0 thì i=6*x + 1 = 1 và i=6*x + 5 = 5
x = 1 thì i=6*x + 1 = 7 và i=6*x + 5 = 11
x = 2 thì i=6*x + 1 = 13 và i=6*x + 5 = 17
x = 3 thì i=6*x + 1 = 19 và i=6*x + 5 = 23
x = 4 thì i=6*x + 1 = 25 và i=6*x + 5 = 27
Từ phân tích trên ta thấy nếu ta bắt đầu với số nguyên tố i=5, thì khi kiểm tra tính chia hết n cho i phải kiểm tra luôn giá trị i+2, sau mỗi lần kiểm tra ta tăng i lên 6 đơn vị.
- Từ những nhận xét trên ta có thuật toán:
* Thuật toán 2: Cách liệt kê:
B1. Nhập số nguyên dương N;
B2. Nếu N = 1 thì N không nguyên tố rồi kết thúc;
B3. Nếu N = 2 hoặc N = 3 thì N là nguyên tố rồi kết thúc;
B4. Nếu (N chia hết cho 2) hoặc (N chia hết cho 3) thì N không nguyên tố rồi kết thúc;
B5. i<-- 5; m <-- [ N ] ;
B6. Nếu i > m thì N là nguyên tố rồi kết thúc;
B7. Nếu (N chia hết cho i) hoặc (N chia hết cho i+2) thì N không nguyên tố rồi kết thúc; 
B8. i <-- i + 6; quay lại B6;
Ví dụ: Khi ta nhập n = 233, ta có [√n] = 15. Để kết luận số 233 là số nguyên tố thì số giá trị cần kiểm tra ở thuật toán 2 giảm rất nhiều so với thuật toán 1:
Thuật toán 1
Thuật toán 2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 2 3 5 7 11 13 17
* Cài đặt bằng Pascal:
function ngto (n : longint): Boolean;
var i , m : longint;
begin
	if (n = 1) then exit(false);
	if (n = 2) or (n = 3) then exit(true);
	if (n mod 2 = 0) or (n mod 3 = 0) then exit(false);
	i := 5; m := trunc(sqrt(n));
	while (i <= m) do
	if (n mod i = 0) or (n mod (i+2) = 0) then exit(false)
	else	inc(i, 6);
	exit(true);
end;
*Nhận xét: Với thuật toán xây dựng trên phương pháp thử chia này thì độ phức tạp của thật toán là O(√n). Tuy thuật toán đã được tối ưu nhưng khi vận dụng chúng ta lưu ý thuật toán đạt hiệu quả tốt khi ta cần kiểm tra tính nguyên tố với số lượng các số không quá lớn và tùy vào giá trị của mỗi số. Ví dụ khi số lượng số cần kiểm tra lên đến 106 và giá trị mỗi số ≤106 ta sẽ phải sử dụng phương pháp khác.
2.3.2.2. Thuật toán sàng nguyên tố Eratosphen
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 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 như sau:
B1: Tạo danh sách các số nguyên từ 2 đến N: (2,3,...,N).
B2: Giả sử tất cả các số trong danh sách đều là số nguyên tố. Trong đó, p=2 là số nguyên tố đầu tiên.
B3: Tất cả các bội số của p: 2p,3p,4p,...sẽ bị đánh dấu vì không phải là số nguyên tố.
B4: Tìm các số còn lại trong danh sách mà chưa bị đánh dấu và phải lớn hơn p. Nếu không còn số nào, dừng tìm kiếm. Ngược lại, gán cho p  giá trị bằng số nguyên tố tiếp theo và quay lại bước 3.
Trong ví dụ sau chúng ta sẽ tìm tất cả các số nguyên tố nhỏ hơn 30. Dãy ban đầu:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Số nguyên tố đầu tiên trong dãy là 2, ta xóa tất cả các bội số (khác 2) của 2, còn lại:
2 3 5 7 9 11 13 15 17 19 21 23 25 27 29
Số tiếp theo trong dãy là 3, ta tiếp tục xóa các bội số của 3, còn lại:
2 3 5 7 11 13 17 19 23 25 29
Lặp lại quá trình trên, ta được dãy các số nguyên tố nhỏ hơn 30:
2 3 5 7 11 13 17 19 23 29
*Nhận xét: 
Tại B3 khi đánh dấu các bội số của p bắt đầu bằng p+p thì sẽ được thay bằng p*p vì các hợp số trước đó nếu là bội của p đã được đánh dấu rồi.
Tại B4 chúng ta cũng lưu ý chỉ tìm các số p chưa được đánh dấu nhỏ hơn hoặc bằng [√n].
 Ví dụ: Ở đây khi đánh dấu các bội số của p= 2 thì ta đã đánh dấu p= 6 nên khi p = 3 ta đánh dấu các bội số của p bắt đầu bằng p*p=9 chứ không phải là p+p=6, khi p=5 ta đánh dấu các bội số của 5 bắt đầu bằng p*p=25 chứ không phải bắt đầu bằng p+p=10( vì 10, 15, 20 là các bội số của 5 thì đã được đánh dấu trước đó,..
Từ đó ta xây dựng thủ tục tìm tất cả các số nguyên tố từ 1 đến n như sau:
const  nmax=n;
VAR f:array[1..nmax] of boolean; n: longint;
procedure sangnt;
var p, j,h: longint
begin
        fillchar(f, sizeof(f),true);
        f[1]:=false; h:= trunc(sqrt(nmax));
        for p:= 2 to h do { xét các số cần kiểm ≤ [√n]}
               if (f[p]) then
 begin 
 j:=p*p; { đây là bước cải tiến bắt đầu j= p*p}
  while (j<=nmax) do 
 begin f[j]:=false;  
 j:=j+p; 
  end;
end;
end;
Bảng các số nguyên tố nhỏ hơn 100
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
*Nhận xét: Độ phức tạp của thuật toán là: O(nlogn). Như vậy trong 1 giây thuật toán có thể thực hiện khi n=107. Thuật toán sàng nguyên tố Eratosphen vận dụng hiệu quả khi cần tìm tất cả các số nguyên tố trong khoảng [a , b] mà khoảng cách a, b là rất lớn. Tuy nhiên khi sử dụng thuật toán này có nhược điểm là tốn nhiều bộ nhớ.
Kết luận: Như vậy, để kiểm tra tính nguyên tố của một số nguyên dương tôi đưa đến 2 giải pháp, hoặc là dùng hàm kiểm tra tính nguyên tố, hoặc là dùng thuật toán sàng nguyên tố Eratosphen. Với 2 giải pháp này tôi hy vọng mang đến cho các em thuật toán tốt để có thể sử dụng trong các cuộc thi lập trình Tin học hay các bài toán trong phạm vi dữ liệu không quá lớn.
2.3.3. Vận dụng giải một số dạng bài toán
2.3.3.1. Bài toán 1
Cho dãy gồm n số nguyên dương ai ( ai ≤ 109, n≤1000). hãy cho biết trong dãy có bao nhiêu số nguyên tố?
 Input: tệp nguyento.inp gồm:
 Dòng đầu tiên là số nguyên dương n
 n dòng tiếp theo mỗi dòng là số nguyên dương ai.
Output: tệp nguyento.out gồm:
 Số nguyên duy nhất là số các số nguyên tố trong dãy.
*Phân tích: Với bài toán này, chỉ cần duyệt từ phần tử đầu tiên đến phần tử cuối cùng, gọi hàm kiểm tra nguyên tố cho từng phần tử, nếu đúng thì tăng biến đếm, nếu sai thì không tăng. Chương trình được viết như sau:
program dem_nguyen_to;
var f1,f2:text;
 dem,n,i:integer; y:longint;
function ngto (x : longint): Boolean;
var j , m : longint;
begin
	if (x = 1) then exit(false);
	if (x = 2) or ( x = 3) then exit(true);
	if (x mod 2 = 0) or ( x mod 3 = 0) then exit(false);
	j:= 5; m := trunc(sqrt(x));
	while (j <= m) do
	if (x mod j = 0) or ( x mod (j+2) = 0) then exit(false)
	else	inc(j, 6);
	exit(true);
end;
BEGIN
assign(f1, 'nguyento.inp'); reset(f1);
assign(f2,'nguyento.out'); rewrite(f2);
dem:= 0;
readln(f1, n);
For i:=1 to n do
 begin
 readln(f1, y);
 if ngto(y) then inc(dem);
 end;
writeln(f2, dem);
close(f1); close(f2);
END.
2.3.3.2 Bài toán 2
Cho số nguyên dương N (2≤N≤109)
Yêu cầu: Phân tích N thành các thừa số nguyên tố dưới dạng N=a*b*c* (với a,b,c là các số nguyên tố)?
Giả sử: cho N = 81: Vì N=81=34 nên biểu diễn dưới dạng tích các thừa số nguyên tố: 3*3*3*3
Dữ liệu vào: Cho trong tệp bai2.inp gồm dòng duy nhất chứa số N
Dữ liệu ra: Ghi ra tệp bai2.out gồm các thừa số được phân tích cách nhau dấu cách.
Ví dụ:
Bai2.inp
Bai2.out
1296
2 2 2 2 3 3 3 3
*Phân tích: Với bài toán này chúng ta vận dụng tương tự các bước trong thuật toán của hàm kiểm tra ngto() để giải quyết, tuy nhiên tại mỗi bước khi kiểm tra số i nếu i là ước của n thì không kết luận "n không là số nguyên tố" mà ta đi lặp việc chia n cho i đến khi nào không chia được nữa thì tăng i lên. Ở đây chúng ta cũng để ý nếu n chia hết cho 2 thì n không chia hết cho bất kì một số chẵn nào nữa, vì vậy tôi tách riêng trường hợp i=2 để khi áp dụng thuật toán bắt đầu i=3 và sau mỗi lần chia liên tiếp n cho i đến khi không chia được nữa thì tăng i lên 2 đơn vị( không tăng i lên 6 đơn vị như thuật toán 2) để bài toán tối ưu hơn.
Chương trình được viết như sau: 
PRPGRAM phantich_ngto;
VAR f1, f2: text; 
n,i: longint;
BEGIN
assign(f1, 'BAI2.INP'); reset(f1);
assign(f2,'BAI2.OUT'); rewrite(f2);
readln(f1, n);
while (n mod 2 = 0) and (n > 1) do
begin
n:= n div 2;
write(f2, 2);
if n > 1 then write( f2, ' ');
end;
i:= 3;
While (n>1) do
 begin 
 while ( n mod i =0) and ( n>1) do 
begin
n:= n div i;
write(f2, i);
if n >1 then write(f2, ' ');
end;
inc(i,2);
end;
close(f1); close(f2);
END. 
2.3.3.3. Bài toán 3: Tổng nguyên tố( Đề thi chọn học sinh giỏi Tỉnh Thanh Hóa năm học 2016 - 2017)
Cho số nguyên dương N (N ≤ 105).
Yêu cầu: Tìm số các cặp số nguyên dương x, y sao cho:
x, y là 2 số nguyên tố.
x + y = N
x ≤ y
Dữ liệu vào: Vào từ file văn bản BAI3.INP gồm một số duy nhất N.
Kết quả: Đưa ra file văn bản BAI3.OUT một số là số các cặp số tìm được.
BAI3.INP
BAI3.OUT
10
2
Ví dụ:
*Phân tích: Với bài toán này thì chúng ta sử dụng hàm kiểm tra nguyên tố ngto() để duyệt đồng thời các cặp số (i, n-i) bắt đầu từ i= 2 đến n div 2, với mỗi cặp số hàm kiểm tra đồng thời cho kết quả true thì ta tăng biến đếm lên một đơn vị, ngược lại thì không tăng. Tuy nhiên ta đã biết 2 là số nguyên tố chẵn duy nhất, vì vậy ta sẽ xét cặp (i=2, n-i) riêng để vào vòng lặp ta xét các cặp (i lẻ, n-i). Chương trình được thực hiện như sau:
VAR f1, f2:text;
 n,i,p,dem: longint;
function ngto(x: longint): boolean; 
var j,m: longint;
begin
if x = 1 then exit(false);
if (x = 2) or (x = 3) then exit(true);
if (x mod 2 = 0) or (x mod 3 = 0) then exit(false);
j:= 5 ; m := trunc(sqrt(x));
while j<= m do 
if (x mod j = 0) or (x mod (j+2)= 0) then exit(false)
else inc(j,6);
exit( true);
end;
BEGIN
assign(f1, 'BAI3.INP'); reset(f1);
assign(f2, 'BAI3.OUT'); rewrite(f2);
readln(f1,n); dem:=0;
if ngto(n-2) then inc(dem); 
i:= 3; p := n div 2;
while i <= p do
begin
if (ngto(i)) and (ngto(n - i)) then inc(dem) ;
i:= i+ 2;
end;
writeln(f2, dem);
close(f1);close(f2);
END.
2.3.3.4. Bài toán 4: Số siêu nguyên tố là số nguyên tố mà khi xóa 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à số nguyên tố.
Dữ liệu: Vào từ file văn bản 'BAI4.INP' gồm: Dòng đầu tiên ghi giá trị n, n dòng tiếp