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.
Nội dung trích xuất từ tài liệu:
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 LỤCI. ĐẶ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: ......................................................... 1II. 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ọngcủ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ưỡnghọ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êntố 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ấthay 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ạmvi 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 1giây, nó chỉ thực sự hiệu quả khi N ≤ 10 . Một cải tiến làm cho sàng 7Eratosthenes có thể hiệu quả khi N ≤ 108trong giới hạn thời gian 1 giây để ápdụ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ụnggiả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ảimột số bài toán trong chương trình bồi dưỡng học sinh giỏi Tin học tại trườngTHPT Thanh Chương 1. 1 II. NỘI DUNG1. Định nghĩa số nguyên tố: Số nguyên tố là số tự nhiên lớn hơn 1 k ...