tailieunhanh - Sáng kiến kinh nghiệm THPT: Nghiên cứu các cải tiến sàng Eratosthenes và áp dụng giải một số bài toán trong chương trình bồi dưỡng học sinh giỏi Tin học

Mục tiêu nghiên cứu của sáng kiến kinh nghiệm là trình bày về sàng Eratosthenes và cách cải tiến sàng Eratosthenes để áp dụng giải một số bài toán liên quan. | MỤC LỤC I. ĐẶT VẤN ĐỀ. 1 1. Lí do chọn đề tài . 1 2. Mục đích của đề tài . 1 3. Nhiệm vụ của đề tài . 1 4. Giới hạn phạm vi nghiên cứu của đề tài . 1 II. NỘI DUNG . 2 1. Định nghĩa số nguyên tố . 2 2. Thuật toán Vét cạn Brute Forces . 2 3. Sàng nguyên tố Eratosthenes . 3 4. Cải tiến 1 . 4 5. Cải tiến 2 . 5 6. Cải tiến 3 . 5 Kết quả sau cải tiến . 7 7. Một số bài toán ví dụ áp dụng. 7 Bài 1 Factor. 7 Bài 2. Tổng các số nguyên tố đầu tiên . 11 Bài 3. Tìm số nguyên tố thứ N. 12 Bài 4 Chú gấu Tommy và các bạn . 14 Bài 5 Hoán đổi. 17 Bài 6 Thuyền trưởng Prime . 20 III. KẾT LUẬN . 25 TÀI LIỆU THAM KHẢO . 26 I. ĐẶT VẤN ĐỀ 1. Lí do chọn đề tài Công tác tự học và tự nghiên cứu là một trong những hoạt động quan trọng của giáo viên nhằm đáp ứng yêu cầu dạy học đặc biệt là trong công tác bồi dưỡng học sinh giỏi. Đối với việc bồi dưỡng học sinh giỏi môn Tin học có khá nhiều chuyên đề bài tập thường gặp trong các kỳ thi. Các bài toán về số học nói chung và số nguyên tố nói riêng là một trong những bài tập thường gặp đó. Trong một số bài toán ta rất hay gặp các yêu cầu mà cần phải xác định được các số nguyên tố trong một phạm vi giới hạn nào đó như xét tính nguyên tố liệt kê các số nguyên tố đếm các số nguyên tố Sàng nguyên tố Eratosthenes là một thuật toán hiệu quả để kiểm tra liệt kê đếm các số nguyên tố trong đoạn 1 N . Tuy nhiên trong giới hạn thời gian 1 giây nó chỉ thực sự hiệu quả khi N 10 . Một cải tiến làm cho sàng 7 Eratosthenes có thể hiệu quả khi N 108trong giới hạn thời gian 1 giây để áp dụng trong một số bài tập sẽ được trình bày trong sáng kiến này. 2. Mục đích của đề tài Trình bày về sàng Eratosthenes và cách cải tiến sàng Eratosthenes để áp dụng giải một số bài toán liên quan. 3. Nhiệm vụ của đề tài Trình bày sàng Eratosthenes và cải tiến sàng Eratosthenes. Một số bài tập áp dụng và hướng dẫn giải. 4. Giới hạn phạm vi nghiên cứu của đề tài Đề tài sáng kiến nghiên cứu các cải tiến sàng Eratosthenes và áp dụng giải một số bài toán trong chương trình bồi dưỡng học