SKKN Á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++

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.
 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 nghiệp hóa, hiện đại hóa. Đề tài giới thiệu về phương pháp Sàng số nguyên tố, một thuật toán tìm số ngyên tố trong một khoảng nhất định, hướng học sịnh giải quyết các bài toán về số nguyên tố dể dàng, linh hoạt, đúng đắn và hiệu quả hơn. Đề tài đã được áp dụng ở trường THPT Nam Đàn 1 có những đóng góp sau:
Giúp học sinh yêu thích môn học lập trình, nắm được phương pháp giải các bài toán cơ bản về số nguyên tố 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ó. Từ đó, giúp việc học trở nên đơn giản và hiệu quả hơn.
Giúp giáo viên không chỉ nắm chắc kiến thức mình dạy mà còn không ngừng nâng cao năng lực CNTT. Phù hợp với tình hình thực tế hiện nay.

PHẦN II. NỘI DUNG NGHIÊN CỨU
1. Cơ sở lý luận.
Khi tiếp cận với kiến thức lập trình của bộ môn tin học, vấn đề đầu tiên và quan trọng nhất là giáo viên phải truyền cho học sinh được niềm đam mê và dạy cho học sinh được cách tư duy logic. Các bài toán về “Số nguyên tố” luôn để lại những vấn đề mới mẻ cho học sinh. Trong chuyên đề này tôi muốn giới thiệu phương pháp Sàng Ơ-ra-tô-xten, đây là phương pháp tìm tất cả các số nguyên tố trong một giới hạn nào đó và phát triển chuyên sâu về chuyên đề này. Từ đó  để vận dụng giải quyết các bài toán mở rộng và phức tạp hơn.
2. Thực trạng của vấn đề.
Trường THPT Nam đàn 1 là ngôi trường ở vùng nông thôn nằm dưới chân đê dải Sông Lam nên đa số học sinh chưa có cơ hội, điều kiện tiếp xúc với công nghệ và máy tính. Vì vậy, tin học là một môn học tương đối lạ lẫm và khó đối với học sinh trường tôi. Đặc biệt là chương trình tin học lập trình, với các em học lập trình còn khó hơn học toán, lí, hóa, .. vì điều kiện cơ sở vật chất của trường còn nhiều khó khăn, học sinh chỉ học chính khóa trên lớp về nhà lại không có máy tính để thực hành. Điều này dẫn đến ý thức tự giác của học sinh chưa cao, đặc biệt là các em học để thi học sinh giỏi lại càng khó. Với đội tuyển học sinh giỏi, hầu hết các em đều chưa có bất kì kiến thức cơ bản nào liên quan đến lập trình, gia đình chưa có máy tính để các em thực hành. Vì vậy giáo viên dạy đội tuyển phải bắt đầu rèn luyện cho các em từ những câu lệnh cơ bản nhất. Trải qua quá trình dạy học và bồi dưỡng học sinh giỏi. Tôi đã đúc rút được kinh nghiệm khi giải quyết các bài toán phức tạp cần chia nhỏ bài toán đó ra thành các mô đun, mỗi mô đun là 1 chương trình con giải quyết 1 việc nào đó, đồng thời biết phân luồng các dạng bài toán tương ứng với các mảng để học sinh dễ giải quyết. Để đáp ứng được sự đổi mới trong thời đại 4.0 tôi đã định hướng cho học sinh chuyển sang ngôn ngữ lập trình C++ thay đổi cho ngôn ngữ lập trình truyền thống pascal. Cơ sở trên đã giúp tôi áp dụng đề tài: “Áp dụng phương pháp sàng Ơ-ra-tô-xten vào giải các bài toán về số nguyên tố trong lập trình C++ “ và chuyên sâu về chuyên đề này để giải các bài toán cơ bản, bài toán khó.
Thực trạng việc bồi dưỡng học sinh giỏi bằng ngôn ngữ lập trình C++ trong các trường phổ thông tại Nam Đàn trong thời gian qua:
Năm học 2020-2021 chúng tôi đã làm một cuộc điều tra nhỏ với 5 trường THPT trên địa bàn huyện Nam Đàn, tỉnh Nghệ An (THPT Nam Đàn I, THPT Nam Đàn 2, THPT Sào Nam, THPT Mai Hắc Đế và THPT Kim Liên) về thực trạng sử dụng  ngôn ngữ lập trình C++ trong bồi giỏi và thi học sinh giỏi tỉnh, có kết quả như sau:
Bảng thông số về việc sử dụng ngôn ngữ lập trình C++ trong bồi giỏi và thi học sinh giỏi tỉnh tại một số trường THPT trên địa bàn huyện Nam Đàn năm học 2020-2021.
TT Tên trường Học sinh thi C++ Học sinh thi Pascal
1 THPT Nam Đàn 1 1(100%) 0
2 THPT Nam Đàn 2 0 1(100%)
3 THPT Kim Liên 1(100%) 0
4 THPT Sào Nam 0 1(100%)
5 THPT Mai Hắc Đế 0 1(100%)
Nhận xét: Các giáo viên chưa thực sự chú trọng việc đưa ngôn ngữ lập trình C++  thay thế cho ngôn ngữ truyền thống Pascal. Trong 5 trường THPT thì có 3 trường học sinh thi bằng ngôn ngữ lập trình Pascal chiếm 60%.
3. Nội dung và giải pháp thực hiện.
Trước hết  tôi đưa ra bài toán như sau:
Bài toán 1. Viết chương trình nhập vào từ bàn phím số nguyên N (N>10), in ra màn hình các số nguyên tố trong khoảng từ 2 đến N.
*Khái niệm số nguyên tố: Một số nguyên dương N là số nguyên tố nếu nó có đúng 2 ước số khác nhau là 1 và chính nó.
Như vậy ta có thể giải bài toán 1 theo cách sau:
C1: Viết một hàm kiểm tra số nguyên k có phải số nguyên tố không  kt(k).
Sau đó cho vòng for chạy i=2 đến N để kiểm  tra  số i là số nguyên tố và in ra. Để cải tiến cần giảm thiểu số các số cần kiểm tra. Thay vì kiểm tra các số i ta sẽ chỉ kiểm tra các số i có tính chất giống tính chất của số nguyên tố.
**Tính chất số nguyên tố:
Trừ số 2 và số 3 các số nguyên tố có dạng  6k 1 ( vì các số có dạng 6k 2 thì chia hết cho 2, 6k 3 thì chia hết cho 3).  vậy  bài toán 1  giải theo cách:  C2: Sử dụng tính chất số nguyên tố.
Phương pháp Sàng nguyên tố  Sàng Ơ-ra-tô-xten (Eratosthene)
Đây là phương pháp để tìm được tất cả các số nguyên tố trong một giới hạn nào đó. Nhà toán học cổ Hi Lạp Ơ-ra-tô-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 dù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 số nguyên tố được giữ lại. Bảng số nguyên tố này được gọi là sàng Ơ-ra-tô-xten.
Ta làm như sau:
Trước hết xóa số 1.
Giữ lại số 2 rồi xóa tất cả các bội của 2 mà lớn hơn 2.
Giữ lại số 3 rồi xóa tất cả các bội của 3 mà lớn hơn 3.
Giữ lại số 5 (số 4 đã bị xóa)  rồi xóa tất cả các bội của 5 mà lớn hơn 5.
Giữ lại số 7 (số 6 đã bị xóa)  rồi xóa tất cả các bội của 7 mà lớn hơn 7.  Các số 8, 9, 10, đã bị xóa. Không cần xóa tiếp các bội của các số lớn hơn 10 cũng kết luận được rằng không còn hợp số nào nữa.
Thật vậy, giả sử n là một hợp số chia hết cho một số a lớn hơn 10 thì do n<100, a>10 nên n phải chia hết cho một số b nhỏ hơn 10, do đó n đã bị xóa.
Tôi đã áp dụng phương pháp sàng Ơ-ra-tô-xten vào để giải hệ thống các bài toán về số nguyên tố trong ngôn ngữ lập trình C++
Trong quá trình lập trình tôi kết hợp sử dụng Vector,  dữ liệu kiểu tập hợp Set chương trình sẽ gọn hơn và hiệu quả hơn.  Một số điểm nổi trội của vector:
– Không cần phải khai báo kích thước của mảng ví dụ: int a[100] …, vì vecter có thể tự động nâng kích thước lên.
– Khi thêm 1 phần tử vào vector đã đầy rồi, thì nó sẽ tự động tăng kích thước của nó lên để dành chỗ cho giá trị mới này.
– Vector còn cho biết số lượng các phần tử lưu trong đó.
– Dùng số phần tử âm vẫn được trong vecter ví dụ A[-6], a[-9], rất tiện trong cài đặt các giải thuật.
Tập hợp Set trong C++
– Cấu trúc dữ liệu kiểu tập hợp (Set) dùng để lưu các phần tử cùng kiểu dữ liệu, trong đó các phần tử không được trùng nhau. Khi chèn mỗi phần tử vào trong Set, Set sẽ kiểm tra và chỉ thêm phần tử đó khi nó không có trong set. Các phần tử được thêm vào được sắp xếp theo thứ tự tăng dần. Do set chỉ chứa các phần tử không trùng nhau, nên ta có thể sử dụng cấu trúc dữ liệu này cho một số bài toán liên quan đến tập hợp như: Cho dãy gồm n phần tử. hãy đếm số phần tử khác nhau trong mảng…
***Thuật toán Sàng nguyên tố Eratosthenes
Void sang()
{ bool f[n+1] ={0};
f[0]=1;    f[1]=1;
For(int i=2; i<=n; i++)
{ If(!f[i])  for(int j=2; i*j <=n; j++)  f[i*j] =1;   }
Return ;   }
Ta có mảng f, f[i]=0 nếu i là số nguyên tố và ngược lại i là hợp số. Thuật toán này chỉ có độ phức tạp là O(n), nên ta hoàn toàn có thể thực hiện với n=108.
4. Các bài toán áp dụng
Bài toán 1: Viết chương trình liệt kê các số nguyên tố trong khoảng từ [2,N]
Dữ liệu vào: từ tệp văn bản nguyento.inp. Chứa duy nhất chỉ số nguyên N (N>=10)
Kết quả:  Ghi vào tệp văn bản nguyento.out các số nguyên tố tìm được, mỗi số cách nhau ít nhất 1 kí tự trống.
NGUYENTO.INP NGUYENTO.OUT
20 2 3 5 7 11 13 17 19
Ý tưởng: Dùng phương pháp sàng số nguyên tố.
– Khởi tạo 1 mảng bool kích thước n+1, với giá trị các phần tử của mảng = 0 (giả sử tất cả các phần tử trong mảng bool là  số nguyên tố).
– Khởi tạo một vector: vt có giá trị int (lưu các phần tử là số nguyên tố).
– Sàng các số từ 2n
+Nếu (!F[i])=1 thì i là số nguyên tố ta đưa i vào vector: vt.
Tạo vòng lặp j=2 đến i*j <=n, f[i*j]=1 để sàng các phần tử là bội của i không phải số nguyên tố.
Dưới đây là ví dụ mô phỏng việc thực hiện ý tưởng trên:  với n=20.