tailieunhanh - Chuyên đề: Sàng nguyên tố cải tiến và ứng dụng

Chuyên đề hướng đến đối tượng là học sinh lớp 10. Do đó hướng đến các cách cải tiến có cài đặt không quá phức tạp để các em tiếp thu tốt. Giới hạn chuyên đề đạt được là N = 108 . Các cách cài đặt tối ưu hơn nhưng phức tạp hơn để đạt được N = 109 , 1010 sẽ được giới thiệu đến trong phần kết luận. Thầy cô đồng nghiệp và các bạn quan tâm có thể tìm hiểu thêm. | SÀNG NGUYÊN TỐ CẢI TIẾN VÀ ỨNG DỤNG 1. Tóm tắt Số học hay còn gọi là lí thuyết số là một trong những ngành toán học cổ nhất của nhân loại. Theo thời gian đã có nhiều thuật toán về số được đề xuất giúp giải quyết các vấn đề về số học như kiểm tra số nguyên tố tìm ước chung lớn nhất mã hóa Đây được xem là những thành tựu to lớn của nhân loại với sự góp mặt của các nhà toán học vĩ đại như Euclid Euler Fermat Trong bồi dưỡng học sinh giỏi Tin học số học giữ vai trò rất quan trọng là kiến thức nền tảng không thể thiếu cho các em. Đặc biệt trong số học sự xuất hiện của nhiều loại số khác nhau có những tính chất đặc biệt như Fibonacci Catalan Số hoàn hảo Số nguyên tố luôn chứa đựng các bí ẩn bên trong qui luật của nó. Ta thử tìm hiểu một vài điều thú vị về số nguyên tố. Như ta đã biết mọi số tự nhiên lớn hơn 1 đều có thể phân tích thành tích các số nguyên tố. Điều này cho thấy từ các số nguyên tố ta có thể xây dựng nên toàn bộ các số tự nhiên. Bên cạnh đó số nguyên tố chính là yếu tố quyết định trong hệ mã hóa công khai RSA được sử dụng rộng rải ngày nay. Số 113 của lực lượng cảnh sát cơ động cũng là số nguyên tố Trong một số bài toán ta rất hay gặp các yêu cầu cần phải xác định được các số nguyên tố trong một giới hạn nào đó như Liệt kê các số nguyên tố tính tổng các số nguyên tố . Với các thuật toán kiểm tra số nguyên tố theo định nghĩa ta không đủ thời gian để xử lý khi khoảng dữ liệu quá lớn. Vì thế một nhóm thuật toán đã ra đời giúp ta liệt kê danh sách các số nguyên tố trong đoạn 1 N bằng cách kiểm tra khả năng nguyên tố của các số nguyên trong đoạn. Nhóm thuật toán này là các Sàng số nguyên tố. Trong khuôn khổ chuyên đề tôi xin trình bày các thuật toán về sàng số nguyên tố như Eratosthenes Atkin và Sundaram. Tôi cũng tiến hành so sánh hiệu năng của các thuật toán với nhau. Tiếp đến tôi sẽ thực hiện cải tiến thuật toán sàng Atkin sàng Eratosthenes để mang lại hiệu suất cao hơn nhưng vẫn dễ cài đặt. Cuối cùng sẽ là một số các bài toán minh họa theo các mức độ khác .