SKKN Rèn luyện kĩ năng giải tốt các bài toán về số nguyên tố cho học sinh khá giỏi

SỞ GIÁO DỤC VÀ ĐÀO TẠO THANH HOÁ 
TRƯỜNG THPT TRIỆU SƠN 3
SÁNG KIẾN KINH NGHIỆM
RÈN LUYỆN KĨ NĂNG GIẢI TỐT CÁC BÀI TOÁN
VỀ SỐ NGUYÊN TỐ CHO HỌC SINH KHÁ GIỎI
Người thực hiện: Lê Thị Sâm
Chức vụ: Giáo viên
Đơn vị công tác: Trường THPT Triệu Sơn 3
SKKN thuộc lĩnh mực (môn): Tin học
THANH HOÁ NĂM 2019
MỤC LỤC
1. MỞ ĐẦU............................1
1.1. Lí do chọn đề tài..........1
1.2. Mục đích nghiên cứu...................1
1.3. Đối tượng nghiên cứu..1
1.4. Phương pháp nghiên cứu.1
2. NỘI DUNG CỦA SÁNG KIẾN KINH NGHIỆM..2
2.1. Cơ sở lí luận của sáng kiến kinh nghiệm.....2
2.2. Thực trạng của vấn đề trước khi áp dụng sáng kiến kinh nghiệm...2
2.3. Các giải pháp đã áp dụng để giải quyết vấn đề...2
2.3.1. Giải pháp 1: Tạo tâm lí hứng thú cho học sinh tiếp cận về số nguyên tố.............2
2.3.2. Giải pháp 2: Tìm hiểu kiến thức liên quan về số nguyên tố.....5
2.3.2.1. Định nghĩa.........5
2.3.2.2. Thuật toán kiểm tra tính nguyên tố của một số nguyên dương..5
2.3.2.3. Thuật toán sàng nguyên tố Ơ-ra-to-Xten(Euratothenes)...5
2.3.3. Giải pháp 3: Vận dụng linh hoạt các thuật toán cơ bản khi giải các bài toán liên quan về số nguyên tố......6
2.3.3.1. Các thuật toán cơ bản mà học sinh có thể vận dụng.....6
2.3.3.2. Các bước khi giải bài toán.6
2.3.4. Giải pháp 4: Hệ thống các bài toán có liên quan về số nguyên tố...12
2.3.5. Giải pháp 5: Rèn luyện kĩ năng làm việc nhóm thông qua mỗi học sinh là một giám khảo .17
2.4. Hiệu quả của sáng kiến kinh nghiệm.....18
3. KẾT LUẬN, KIẾN NGHỊ.....19
3.1. Kết luận.............19
3.2. Kiến nghị...19
Tài liệu tham khảo....20
1. MỞ ĐẦU
1.1. Lí do chọn đề tài
Số nguyên tố là một chuyên đề khó và “bí ẩn” cho nhiều nhà khoa học nên nó được nghiên cứu từ rất lâu. Người ta tìm ra nhiều điều lí thú về số nguyên tố và áp dụng vào thực tiễn có nhiều hiệu quả, nhất là trong lĩnh vực hệ mật mã công nghệ thông tin. Số nguyên tố được đưa vào chương trình toán trung học cơ sở để giảng dạy nên được nhiều giáo viên dạy toán học quan tâm. Do đó nhiều sáng kiến trong lĩnh vực toán được nghiên cứu như: “Số ngyên tố và các dạng liên quan” của tác giả Nguyễn Minh-giáo viên tổ Toán-Lí-Tin trường THCS Quang Trung; sáng kiến “Số nguyên tố trường THCS đối với đối tượng là học sinh khá giỏi” của tác giả Lê Đình Huân trường THCS Tam Dị 2Tuy nhiên đối với môn Tin học thì các sáng kiến về số nguyên tố rất hạn chế. Trong khi đó các đề thi học sinh giỏi môn Tin học các cấp về số nguyên tố luôn được chú ý đặc biệt. Các dạng bài tập về số nguyên tố được biến đổi đa dạng và phong phú. Bởi vậy, tôi rất trăn trở muốn tìm hiểu, nghiên cứu và xây dựng một chuyên đề về số nguyên tố làm tài liệu cho bản thân trong quá trình ôn luyện học sinh giỏi và mong muốn chia sẻ với quý đồng nghiệp hoàn thiện hơn nữa chuyên đề này.
Từ những lí do trên cùng với kinh nghiệm giảng dạy tôi đã quyết định chọn đề tài: “Rèn luyện kĩ năng giải tốt các bài toán về số nguyên tố cho học sinh khá giỏi’’ làm đề tài sáng kiến kinh nghiệm của bản thân trong năm học 2018 -2019. Rất mong nhận được sự đóng góp ý kiến, nhận xét và đánh giá của quý đồng nghiệp để đề tài được hoàn thiện hơn. 	
1.2. Mục đích nghiên cứu
- Các phương pháp giúp học sinh giải tốt các bài tập về số nguyên tố
- Nghiên cứu đề tài này với mong muốn đây là một tài liệu nâng cao hiệu quả của môn học cho học sinh khi tham gia học sinh giỏi các cấp
1.3. Đối tượng nghiên cứu
- Số nguyên tố
- Các bài tập về số nguyên tố trong SGK Tin học 10 và Tin học 11
- Các bài tập về số nguyên tố trong các kì thi học sinh giỏi ở nhiều tỉnh khác nhau
1.4. Phương pháp nghiên cứu 
- Phương pháp nghiên cứu xây dựng cơ sở lí thuyết: Tìm đọc, nghiên cứu, phân tích các tài liệu liên quan. Rút kinh nghiệm trong thực tiễn giảng dạy. Từ đó xây dựng cơ sở lí luận của đề tài.
- Phương pháp khảo sát thực tế, thu thập thông tinTừ đó đề ra những giải pháp phù hợp để nâng cao hứng thú học môn Tin học cho học sinh.
2. NỘI DUNG CỦA SÁNG KIẾN KINH NGHIỆM
2.1. Cơ sở lí luận của sáng kiến kinh nghiệm
Trong nghiên cứu khoa học thì việc tìm ra quy luật, phương pháp để giải quyết một vấn đề là vô cùng quan trọng. Nó giúp ta có định hướng tìm được lời giải của một lớp các bài toán. Trong dạy học giáo viên là người có vai trò thiết kế và điều khiển sao cho học sinh thực hiện và luyện tập các hoạt động tương thích với nội dung dạy học. Vì vậy, trang bị về phương pháp, tập trung dạy cách học, rèn luyện các kĩ năng, phát triển các năng lực cho học sinh... là một nhiệm vụ quan trọng của người giáo viên.
	SGK tin học 10 chỉ đề cập duy nhất một ví dụ về thuật toán kiểm tra tính nguyên tố của một số nguyên dương. Nhưng xoay quanh thuật toán này các bài tập về số nguyên tố, đề thi số nguyên tố trong nhiều kì thi học sinh giỏi các cấp thì lại vô cùng đa dạng. Tôi theo dõi đề thi học sinh giỏi của tỉnh Thanh Hóa trong các năm gần đây thì có nhiều năm đề cập đến nội dung này, đó là vào năm học 2014-2015 với bài 2 là bảo vệ mật khẩu máy tính, năm học 2016-2017 với bài 1 là tổng nguyên tố, năm học 2017-2018 với bài tập 3 về dãy số Ham-ming; Đề thi học sinh giỏi lớp 12 tỉnh Quảng Trị năm học 2017-2018 với bài 3 là số siêu nguyên tố;  Vì vậy, tôi nhận thấy mình cần bổ sung thêm một số giải pháp giúp học sinh dễ dàng giải quyết dạng bài toán này. 
2.2. Thực trạng của vấn đề trước khi áp dụng sáng kiến kinh nghiệm
Trường THPT Triệu Sơn 3 là một trường nằm ở phía tây của huyện Triệu Sơn, có nhiều xã miền núi, đặc biệt khó khăn như: xã Thọ Bình, Triệu Thành, Bình Sơncó nhiều học sinh là con em dân tộc thiểu số nên điểm đầu vào thấp. Tư duy của học sinh chậm, điều kiện kinh tế còn khó khăn, đường đi học còn xa và khó đi nên ảnh hưởng rất nhiều đến kết quả học tập của các em. 
Do đặc thù bộ môn Tin học là môn học khá mới mẻ, học lập trình với các em trở nên xa lạ. Khi chọn các em vào đội tuyển học sinh giỏi thì các em đều khá bỡ ngỡ, tư duy cũng hạn chế do nguồn học sinh ít. Do vậy, việc các em giải tốt các bài toán về lập trình gặp nhiều khó khăn.
Năm học 2016- 2017 và năm học 2017-2018 thì các em trong đội tuyển học sinh giỏi của trường đều chạy không hết test các bài toán về số nguyên tố trong đề thi học sinh giỏi cấp tỉnh.
2.3. Các giải pháp đã áp dụng để giải quyết vấn đề
2.3.1. Giải pháp 1: Tạo tâm lí hứng thú cho học sinh tiếp cận về số nguyên tố
	Nói về số nguyên tố đây là một chuyên đề khó, nhất là khi các em tham gia thi học sinh giỏi các cấp. Qua nhiều năm giảng dạy bản thân tôi cũng rất trăn trở về vấn đề này. Làm sao để các em tiếp cận chuyên đề với tâm lí thoải mái, tự tin? Làm sao để có một hệ thống bài tập logic, tìm ra phương pháp giải đơn giản, hiệu quả? SGK tin học 10 có đưa thuật toán kiểm tra tính nguyên tố của một số nguyên dương để giảng dạy. Tìm hiểu thuật toán này tôi thiết nghĩ đây là một thuật toán khó nhất là khi các em mới làm quen với khái niệm “thuật toán” nên nếu giáo viên trình bày thuật toán ngay thì rất dễ tạo tâm lí “nản” đối với trò. Bởi vậy, bản thân tôi khi cho các em tìm hiểu thuật toán này trước hết tôi cho các em tìm hiểu những điều thú vị về số nguyên tố trong buổi đầu khi dạy chuyên đề với mục đích tạo tâm lí “thoải mái” và “thân thiện” khi tiếp cận nội dung này. 
Ví dụ 1: VE SẦU MAGICICADA (Nguồn: S&V Junior -Theo Tạp chí Tia Sáng 12. 2002)
Hiện nay, ở miền Đông nước Mĩ có ba dòng ve sầu Magicicada có cách sống rất kỳ lạ. Sau khi giao phối, ve sầu chui xuống đất đẻ trứng vào gốc cây to rồi bỏ đi. Ấu trùng ve sầu ở lì lại đó suốt 13 hoặc 17 năm liền. Sau một thời gian dài sống nhờ rễ cây như vậy, ấu trùng nở thành ve sầu và chui lên mặt đất, cặp đôi, đẻ trứng rồi chết đi... Và thế hệ con lại tiếp tục chu kì 17 năm hoặc 13 năm của mình. Theo một số nhà nghiên cứu, chu kì 13 và 17 năm (hai số nguyên tố) là yếu tố sống còn của một số loại ve sầu. Lập luận của họ như sau: chim và động vật ăn mồi thích ve sầu có chu kì sống khoảng 2 đến 5 năm; với chu kì sống 13 hoặc 17 năm, rất lâu sau ve sầu mới phải sống cùng thời gian phát triển đông nhất của kẻ thù ăn thịt mình. Ví dụ, cứ 17 x 3 = 51 năm, hoặc 13 x 5 = 65 năm thì mới trùng nhau. Như vậy, một "chu kì sống nguyên” giúp ve sầu giảm nguy cơ phải sống cùng kẻ thù của mình. Để có được khả năng này, chắc chắn ve sầu phải trải qua một quá trình tiến hóa dài. Sau nhiều thế hệ, chỉ có những ve sầu có chu kì sống là một số nguyên tố mới có khả năng tồn tại đến ngày hôm nay.
 Một con ve sầu Magicicada thoát ra khỏi bọc nhộng sau 17 năm phát triển ấu trùng.
Ví dụ 2: MẬT MÃ (Nguồn: S&V Junior -Theo Tạp chí Tia Sáng 12. 2002)
Trong suốt nhiều thế kỉ, kĩ thuật mã hóa dựa theo phương pháp cổ truyền: sử dụng một mật mã (có thể là một từ, một văn bản đối chiếu, một dãy số...) để bảo mật thông tin. Người nhận, được người gửi cho biết mật mã, chỉ cần áp dụng quá trình ngược lại là có thể hiểu được thông tin của chúng ta đã bị mã hóa.
	Theo các chuyên gia, đây là phương pháp hai chiều, tức là sử dụng một mật mã để làm hai việc là mã hóa và giải mã. Kĩ thuật này có một nhược điểm là độ bí mật tuyệt đối của mật mã không được đảm bảo. Vì trên thực tế, người gửi phải thông báo cho người nhận mật mã thông qua một hình thức nào đó. Ví dụ, nếu ta muốn chuyển một thông tin mã hóa nào đó cho một người ở rất xa thì ta phải chuyển văn bản chứa đựng thông tin được mã hóa và mật mã cho người đó bằng thư, điện thoại, hoặc Internet và chính vì thế mật mã của bạn (không được mã hóa) sẽ dễ bị người khác biết. Để đảm bảo độ bí mật, người ta đã áp dụng nguyên lí số nguyên tố. Như chúng ta biết, số nguyên tố rất đặc biệt vì chúng là một số nguyên chỉ chia hết cho 1 và chính nó. Ta dễ dàng thực hiện phép nhân giữa các số nguyên tố với nhau. Ví dụ, ai cũng có thể nhân được 319489 x 242483 = 774707470337. Nhưng quá trình ngược lại lại rất phức tạp. Ví dụ, để kiểm tra xem số 267281174273 có phải là số nguyên tố hay không, ta phải mất rất nhiều thời gian với hàng loạt phép tính mới có thể phát hiện được số này là kết quả của phép nhân giữa 274177 với 974849. Mà đây mới chỉ là những số có ít chữ số. Các bạn hình dung nếu kết quả ban đầu là một số có 20, 30 hay 50 chữ số thì khối lượng các phép toán sẽ khổng lồ đến mức nào! Ngược lại với các phương pháp hai chiều hay còn gọi là đối xứng, mô hình số nguyên tố cho phép dễ dàng mã hóa thông tin nhưng dường như là không thực hiện được quá trình ngược lại. Ví dụ, chúng ta có thể chọn hai số nguyên tố p và q bất kì sau đó nhân chúng với nhau để thu được kết quả N. N chính là mật mã và ai cũng có thể biết được mật mã này và sử dụng nó để khóa một thông tin ai đó gửi cho bạn nhưng không ai biết được kết quả N là phép nhân hai số p và q (hai yếu tố không thể thiếu để giải mã và chỉ có bạn biết) nên không thể đọc được thông tin mã hóa của bạn. Phương pháp này vừa dễ thực hiện mà độ bảo mật lại rất cao. Dựa trên nguyên tắc này, các nhà lập trình và quản lí mạng máy tính đã nghĩ ra một hệ thống mã hóa đáp ứng được hai yêu cầu cơ bản là dễ sử dụng và độ bảo mật cao của các thông tin trên mạng Internet mang tên RSA (RSA là tên viết tắt của các thành viên sáng lập: Rivest, Shamir và Adleman lấy từ ba chữ cái đầu của ba tên tác giả. Thuật toán lần đầu được mô tả vào năm 1977 tại học viện công nghệ Massachusetts). 
 Qua hai ví dụ tôi nhận thấy các em rất hào hứng và thích thú muốn tìm hiểu về số nguyên tố. 
	Từ đó lí giải vì sao các em cần tìm hiểu về số nguyên tố? Và tôi đặt ra cho các em những câu hỏi xoay quanh về số nguyên tố như: Số nguyên tố có kì diệu hay không? Có thú vị hay không? Tại sao số nguyên tố lại làm “đau đầu” nhiều nhà toán học trên thế giới? Số nguyên tố được ứng dụng vào cuộc sống như thế nào? Tại sao các bài toán liên quan đến số nguyên tố hay được “chú ý” trong các kì thi học sinh giỏi các cấp? 
	Sau đó tôi chốt lại vấn đề: Có thể nói số nguyên tố đã được tìm hiểu từ rất lâu đời nhưng nó luôn chứa ẩn những điều thú vị cho những nhà nghiên cứu ví dụ vòng đời của chú ve sầu Magicicada. Đặc biệt số nguyên tố được ứng dụng quan trọng trong hệ mật mã RSA với việc mã hóa và bảo mật thông tin. Ba nhà sáng lập: Rivest, Shamir và Adleman khi nghiên cứu hệ mật mã RSA đi sâu vào bài toán “phân tích một số nguyên ra thành tích các thừa số nguyên tố”. Đây là thuật toán đầu tiên phù hợp với việc tạo ra chữ kí điện tử đồng thời với việc mã hóa. RSA được sử dụng phổ biến trong thương mại điện tử. Ngoài ra ứng dụng được sử dụng rộng rãi trong lĩnh vực Tài chính- Ngân hàng như: RSA mã hóa trên thẻ ATM. Xét về mức độ an toàn dựa trên thuật toán, thì giải pháp sử dụng thuật toán RSA luôn có độ tin cậy cao. Đây là điểm đáng lưu tâm trong bối cảnh nguy cơ rủi ro an ninh an toàn thông tin như hiện nay.
Nhận thức được tầm quan trọng và bảo mật thông tin, Ngân hàng Đầu tư và Phát triển Việt Nam (BIDV) đã nghiên cứu và đầu tư về bảo mật hệ thống công nghệ thông tin, đặc biệt, là giải pháp xác thực hai yếu tố RSA cho hệ thống ngân hàng cốt lõi corebanking và một số giải pháp bảo mật khác cho các ứng dụng phục vụ bảo mật cho các giao dịch của ngân hàng. Ứng dụng này giúp cho quá trình giao dịch giữa ngân hàng và khách hàng trở nên đơn giản, gọn nhẹ. Điều đó cho thấy tầm quan trọng của số nguyên tố được ứng dụng trong thực tiễn. Bởi vậy số nguyên tố luôn là một chuyên đề được “quan tâm” trong kì thi học sinh giỏi các cấp. Có thể đây là một tiền đề cho học sinh có lòng đam mê môn tin học trở thành những kĩ sư công nghệ thông tin trong tương lai.
2.3.2. Giải pháp 2: Tìm hiểu kiến thức liên quan về số nguyên tố 
2.3.2.1. Định nghĩa
Số nguyên tố là số tự nhiên lớn hơn 1, chỉ có hai ước là 1 và chính nó.
Hợp số là số tự nhiên lớn hơn 1, có nhiều hơn hai ước.
2.3.2.2. Thuật toán kiểm tra tính nguyên tố của một số nguyên dương
*Ý tưởng thuật toán
- Nếu N<2 thì N không là số nguyên tố.
- Nếu N>=2 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
B1: Nếu N<2 thì thông báo N không nguyên tố rồi kết thúc;
B2: i ←2;	
B3: Nếu i> thì thông báo N là số nguyên tố rồi kết thúc; 
B4: 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;
B5: i← i+1 rồi quay lại bước 3; 
2.3.2.3. Thuật toán Sàng nguyên tố Ơ-ra-to-Xten(Euratothenes)
Nhà toán học cổ HiLạp Ơ-ra-to-Xten(thế kỉ III trước Công nguyên) là người đầu tiên tìm ra cách làm này. Ông viết các số trên giấy cỏ sậy căng trên một cái khung rồi rùi thủng các hợp số được một vật tương tự như cái sàng, các hợp số được sàng qua, các nguyên tố được giữ lại. Bảng số này gọi là Sàng Ơ-ra-to-Xten.
Để tìm các số nguyên tố nhỏ hơn hoặc bằng số tự nhiên N bằng sàng Eratosthenes, ta làm như sau:
B1: Tạo 1 danh sách các số tự nhiên liên tiếp từ 2 đến n: (2, 3, 4,..., 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 B3;
Khi giải thuật kết thúc, tất các số chưa bị đánh dấu trong danh sách là các số nguyên tố cần tìm.
Vì đây là hai thuật toán cơ bản xuyên suốt chuyên đề khi các em tìm hiểu về số nguyên tố nên tôi yêu cầu các em nắm vững và hiểu bản chất của hai thuật toán này. Bởi đây là hai thuật toán được ví như “chìa khóa vàng” mở ra thế giới “bài toán về số nguyen tố”. 
2.3.3. Giải pháp 3: Vận dụng linh hoạt các thuật toán cơ bản khi giải các bài toán liên quan về số nguyên tố
2.3.3.1. Các thuật toán cơ bản mà học sinh có thể vận dụng
- Thuật toán: tìm Max; Min
- Thuật toán: UCLN, BCNN
- Thuật toán tìm kiếm
- Thuật toán sắp xếp bằng tráo đổi hay còn gọi là sắp xếp nổi bọt (Bubble Sort)
- Thuật toán sắp xếp nhanh Quicksort 
2.3.3.2. Các bước khi giải bài toán 
Bước 1: Hướng dẫn học sinh chú ý phạm vi giá trị của biến trong mỗi bài toán (Cách tổ chức dữ liệu)
	Khi giải quyết một bài toán thi học sinh giỏi thì phạm vi giá trị của biến cực kì quan trọng. Bởi yêu cầu của bài toán không còn đơn giản nữa mà phức tạp lên rất nhiều. Điều này quyết định trong mỗi bài toán các em có thể lấy điểm ở hết các test hay không. Thông thường trong thời gian “hạn chế của thi cử” các em chỉ thử được với những bộ dữ liệu đầu vào nhỏ.
Bước 2: Lựa chọn thuật toán 
	Có thể nói bước này rất quan trọng để giải quyết một bài toán có triệt để hay không. Bởi một bài toán thì có thể có nhiều cách giải khác nhau nhưng chọn được thuật toán tốt là cả một quá trình rèn luyện và đúc rút không ngừng. Điều này là một cơ sở để phân biệt được học sinh có “khả năng” và “tố chất tin học” hay không. Các bạn cứ hình dung một người thám hiểm để đi được từ điểm xuất phát đến điểm đích có thể có nhiều con đường khác nhau nhưng người thám hiểm nhanh nhẹn, hoạt bát là người biết chọn con đường “ngắn nhất” và “dễ đi nhất”. Để có một phán đoán tốt trong khi người thám hiểm chưa từng đi bao giờ thì trước đó người thám hiểm cũng đã phải trải qua “những bước tập duyệt rất gian khổ” và đã có những “kĩ năng” nhất định thực tiễn. 
	Khi giải quyết một bài toán bất kì thông thường tôi yêu cầu các em xây dựng một thuật toán tốt. Một thuật toán tốt là thuật toán có thể đáp ứng được các yêu cầu như: không gian lưu trữ, bộ dữ liệu đầu vào, thời gian chạy các testđặc biệt có thể lấy điểm hết ở các test nhất là các test có bộ dữ liệu đầu vào lớn. Việc thiết kế thuật toán tốt có thể mất nhiều thời gian lúc đầu nhưng mang lại hiệu quả cao về sau bởi nếu gặp một bài toán mà các em chỉ biết chăm chăm code thì khi gặp lỗi các em sẽ rất lúng túng không biết lỗi ở bước nào. Đặc biệt trong khi làm bài thi các em còn bị áp đặt về mặt thời gian. Điều này càng làm cho các em bị “rối” khi sửa thuật toán. Vì vậy, ban đầu xác định thuật toán tốt có thể làm các em “đau đầu” nhưng lại rất “nhẹ nhàng” về sau cho các em khi code bài toán. Với đối tượng là học sinh khá giỏi nên ở bước này thay vì trình bày thuật toán theo từng bước hoặc sơ đồ khối như SGK Tin học 10 trình bày thì tôi yêu cầu các em trình bày theo hướng ý tưởng giải thuật nhằm rèn luyện cho các em tư duy giải thuật nhanh và chính xác. 
Bước 3: Lập trình cho bài toán 
	Khi các em đã xác định được thuật toán tốt và kĩ năng lập trình thì bước này không còn gì là khó khăn nữa. Sau đây là một số ví dụ thể hiện các bước khi giải bài toán như trên:
Ví dụ 1: Nguồn bài 1 Đề thi chọn học sinh giỏi tỉnh Đồng Tháp năm học 2012-2013 
Cho dãy số nguyên dương A gồm N phần tử (0<N<=100000, 0<ai<100000, i=1..N)
Yêu cầu: Tìm tất cả các số nguyên tố khác nhau là phần tử của dãy A.
Dữ liệu vào: Cho từ file văn bản SNT.INP gồm:
- Dòng đầu ghi số phần tử N của dãy.
- Dòng thứ i trong số N dòng tiếp theo ghi giá trị của phần tử ai (i=1..N).
Kết quả: 
Ghi vào file văn bản SNT.OUT giá trị các số nguyên tố tìm được theo thứ tự giảm dần, mỗi số ghi trên một dòng. Nếu dãy A không có phần tử nào là số nguyên tố thì ghi ra số 0. 
Ví dụ:
SNT.INP
SNT.OUT
6
2
11	
4
5
9
5
11
5
2
Để giải quyết bài toán này ta cần phân tích bài toán như sau:
Bước 1: Tổ chức dữ liệu 
+ Dãy có N phần tử (N<=100000). Cần mảng 100000 phần tử;
+ Các ai<=100000 nên sử dụng kiểu longint;
Bước 2: Lựa chọn thuật toán 
*Ý tưởng giải thuật 
- Xây dựng hàm kiểm tra nguyên tố;
- Sắp xếp lại dãy số theo thứ tự tăng dần;
- Duyệt từ vị trí N về vị trí thứ 1. Nếu mỗi phần tử là nguyên tố và a[i]a[i+1] thì write(a[i]);
Bước 3: Lập trình giải bài toán 
(Code tham khảo)
Program Nguyen_to_khac_nhau;
var f1,f2:text;
a:array[1..1000000] of longint;
n,i:longint;	
Function Ktnt(n:longint):boolean;
var j:longint;
begin
 if n<2 then exit(false);
 for j:=2 to trunc(sqrt(n)) do
	 if n mod j=0 then exit(false);
	 exit(true);
end;
Procedure HD(var x,y:longint);
var tg:longint;
 begin
	 tg:=x;
	 x:=y;
	 y:=tg;
 end;
Procedure Quicksort(l,r:longint);
var i,j,x:longint;
begin
	i:=l;
	j:=r;
	x:=a[(l+r) div 2];
	repeat
	while a[i]<x do inc(i);
	while a[j]>x do dec(j);
	if i<=j then
 	 begin
 	 HD(a[i],a[j]);
 	 inc(i);
 	 dec(j);
 	 end;
 until (i>j);