SỞ GIÁO DỤC VÀ ĐÀO TẠO NGHỆ AN
TRƯỜNG THPT NAM ĐÀN 1
SÁNG KIẾN KINH NGHIỆM
“ÁP DỤNG PHƯƠNG PHÁP SÀNG ERATOSTHENE
VÀO GIẢI CÁC BÀI TOÁN VỀ SỐ NGUYÊN TỐ
TRONG NGÔN NGỮ LẬP TRÌNH C++”
MÔN: TIN HỌC
Tác giả: Bùi Thị Hồng
Tổ: Tự nhiên 1
Điện thoại: 0396036370
Năm học: 2021-2022
1
MỤC LỤC
TT
Nội dung
Trang
PHẦN 1
PHẦN MỞ ĐẦU
3
1
Lý do chọn đề tài
3
2
Mục tiêu đề tài
3
3
Nhiệm vụ đề tài
4
4
Đối tượng và phương pháp nghiên cứu
4
5
Tính đổi mới và đóng góp của đề tài
4
PHẦN 2
NỘI DUNG NGHIÊN CỨU
6
1
Cơ sở lý luận
6
2
Thực trạng của vấn đề
6
3
Nội dung và giải pháp thực hiện
7
4
Các bài toán áp dụng
9
Bài toán 1: Liệt kê các số nguyên tố
9
Bài toán 2: Tìm số
11
Bài toán 3: Khóa số
14
Bài toán 4: Tìm số Fibonacci nguyên tố
16
Bài toán 5: Vòng số nguyên tố
18
Bài toán 6: Dãy số đặc biệt
20
Bài toán 7: Biểu diễn số
22
Bài toán 8: Dãy nguyên tố
25
Bài toán 9: Siêu nguyên tố
27
Bài toán 10: Phân tích thừa số nguyên tố
29
Bài toán 11: Số nguyên tố Mersen
31
Bài toán 12: Beauty
34
Bài toán 13: Số nguyên tố đối xứng
36
2
Bài toán 14: Dãy con tăng nguyên tố
39
5
Một số kết quả đạt được
41
6
Đóng góp của đề tài
44
PHẦN 3
KẾT LUẬN
45
1
Quá trình nghiên cứu
45
2
Ý nghĩa, tác dụng của đề tài
45
3
Kiến nghị đề xuất
45
TÀI TIỆU THAM KHẢO
46
3
PHẦN I. ĐẶT VẤN ĐỀ
1. Lý do chọn đề tài
Khoa học luôn phát triển, công nghệ được cải tiến hàng ngày góp phần lớn
thúc đẩy xã hội hiện đại hơn. Bởi vậy, Giáo dục cũng phải thay đổi nhằm đáp ứng
được yêu cầu cấp thiết của 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.
Mọi thứ đều có điểm khởi đầu của nó, với học sinh việc học Pascal là bắt đầ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ư ích lợi của các chương trình hoạt động trong máy
tính, các máy tự động. Tuy nhiên để phát huy tốt nhất tiềm năng, khả năng sáng tạo
của mỗi cá nhân thì trong dạy học cần có một sự thay đổi, cải tiến trong giáo dục,
đó là định hướng cho các em một ngôn ngữ lập trình mới. Hiện nay đã có rất nhiều
ngôn ngữ lập trình được tạo ra nhằm phục vụ cho nhiều mục đích khác nhau.
Những ngôn ngữ lập trình mới luôn đem lại đặc điểm, tính năng phù hợp cho các
nhu cầu, vấn đề hiện đại. Nhưng trong đó vẫn có một ngôn ngữ lập trình đã xuất
hiện từ lâu nhưng vẫn còn phát triển mạnh mẽ đến hiện nay đó là ngôn ngữ lập
trình C++. C++ có một hiệu suất cao cùng khả năng tiêu tốn ít tài nguyên phần
cứng khiến chương trình chạy nhanh hơn. Chính vì vậy tôi đã định hướng cho học
sinh chuyển sang học ngôn ngữ này để lập trình giải các bài toán.
Các bài toán về “Số nguyên tố” luôn để lại những vấn đề mới mẻ cho người đọc.
Trong các bài toán hóc búa, thú vị hầu hết là bài toán về số nguyên tố. Từ trước
công nguyên, Ơclít đã khẳng định số nguyên tố là phạm trù cơ bản của số học.
Thực tế đã chứng minh, toán học dù phát triển đến đâu thì vai trò của số nguyên tố
cũng không hề thay đổi. Nó vẫn là một vùng đất kì lạ dù bao năm qua đã có nhiều
người thám hiểm. Do vậy không thể tránh khỏi hiện tượng các em học sinh lo sợ
khi gặp các bài toán về số nguyên tố, đa phần các em không định hình được
phương pháp giải. Đây cũng chính là lý do mà tôi chọn nghiên cứu đề tài: Phương
pháp giải các bài toán về “Số nguyên tố ” trong ngôn ngữ lập trình C++.
Tôi chỉ là một giáo viên mới chập chững bước vào công việc nghiên cứu khoa học,
với rất ít tài liệu cùng với sự hiểu biết nhỏ bé của mình trong quá trình bồi dưỡng
học sinh giỏi tỉnh mong rằng đề tài này sẽ không nhàm chán mà có thể hữu ích một
phần nhỏ trong việc giải quyết các bài toán dể dàng, linh hoạt, đúng đắn hơn.
2. Mục tiêu đề tài
+ Với giáo viên:
Hỗ trợ giáo viên trong lập trình giải các bài toán về số nguyên tố một
cách nhanh chóng và chính xác.
Phục vụ việc bồi dưỡng HSG.
+ Với học sinh.
4
Học sinh thấy được sự liên kết giữa các môn học, thấy được ứng dụng
của lý thuyết Toán học và ngôn ngữ lập trình trong Tin học vào thực tiễn.
Học sinh được tiếp cận với tri thức trong nhiều lĩnh vực, đem lại nhiều
điều mới mẻ và hứng thú hơn trong học tập.
Giúp ôn thi HSG.
Tìm hiểu lí thuyết chung về số nguyên tố để bổ sung thêm một số kiến
thức giúp cho việc cho việc giải quyết các bài toán trong phần này.
Hướng cho học sinh phương pháp giải các bài toán cơ bản trên cơ sở đó
giải quyết được các bài toán với những hình thức biến tướng của nó.
3. Nhiệm vụ đề tài
Giúp học sinh thấy được sự gần gũi giữa Toán học với Tin học lập trình, từ
đó thấy được sự yêu thích cách tư duy logic của bộ môn này. Đề tài giới thiệu về
phương pháp Sàng số nguyên tố và phát triển chuyên sâu vào chuyên đề này trong
bồi dưỡng học sinh giỏi.
4. Đối tượng và Phương pháp nghiên cứu
- Học sinh giỏi ở các trường THPT bước vào học môn Tin học lập trình, thi
học sinh giỏi trường, từ đó phát triển làm tốt các bài toán trong các kỳ thi học sinh
giỏi Tỉnh ở bậc trung học phổ thông.
- Nghiên cứu, khảo sát thực trạng, nhu cầu của học sinh đối với môn học lập
trình.
- Nghiên cứu thực tiễn công tác tổ chức hoạt động dạy học trong nhà trường
và các văn bản hướng dẫn thực hiện chương trình dạy học hiện nay.
- Tìm hiểu tâm lý học lứa tuổi gắn liền với nhiệm vụ dạy học.
- Tổ chức khảo sát: khảo sát đánh giá mức độ đáp ứng các yêu cầu hoạt động
giáo dục.
- Tham khảo ý kiến của các đồng nghiệp và cốt cán đầu ngành về lĩnh vực
giáo dục và CNTT. Tham khảo các tài liệu về sáng kiến kinh nghiệm và một số tại
liệu liên quan.
- Tham khảo tài liệu, nghiên cứu các đề thi, các bài toán thiên về tư duy toán
học cơ bản chuyển về bài toán lập trình,...
- Có tham khảo các tài liệu về ngôn ngữ lập trình C++, một số đề thi HSG
trường và tỉnh và tài lệu về sáng kiến kinh nghiệm.
5. Tính mới và đóng góp của đề tài
Việc chuyển đổi từ ngôn ngữ lập trình Pascal sang ngôn ngữ lập trình C++
tại trường THPT nâng cao hiệu quả hoạt động giáo dục, đáp ứng các yêu cầu đổi
mới giáo dục hiện nay nhằm đẩy mạnh ứng dụng CNTT vào hỗ trợ đổi mới nội
dung, phương pháp dạy và học góp phần đổi mới căn bản và toàn diện đáp ứng yêu
cầu của cuộc cách mạng Công nghiệp đưa Việt Nam trở thành quốc gia Công