Một số dạng bài toán về ước số và hướng giải quyết trong ôn luyện học sinh giỏi tin học 11

Nội dung tài liệu: Một số dạng bài toán về ước số và hướng giải quyết trong ôn luyện học sinh giỏi tin học 11

1. MỤC LỤC 1. Tên sáng kiến ...............................................................................................2 2. Ngày sáng kiến được áp dụng lần đầu.......................................................2 3. Các thông tin cần bảo mật (nếu có) ...........................................................2 4. Mô tả các giải pháp cũ thường làm ...........................................................2 5. Sự cần thiết phải áp dụng giải pháp sáng kiến:........................................2 6. Mục đích của giải pháp sáng kiến:.............................................................2 7. Nội dung: ......................................................................................................2 7.1. Thuyết minh giải pháp mới .....................................................................2 I. Các bước tiến hành giải pháp .................................................................2 II. Cơ sở lý thuyết ........................................................................................2 2.1. Ước số................................................................................................2 2.2. Ước chung lớn nhất...........................................................................2 III. Các giải pháp đã tiến hành để giải quyết vấn đề................................2 3.1. Dạng 1: Bài toán liên quan đến số ước và tổng các ước của N. .....2 3.1.1.Giải pháp 1: Tiếp cận trực tiếp. ..................................................2 3.1.2. Giải pháp 2. Tiếp cận gián tiếp thông qua sàng nguyên tố. .....2 3.1.3. Bài tập áp dụng...........................................................................2 3.2. Dạng 2: Liệt kê các ước của N..........................................................2 3.2.1. Giải pháp 1: Tiếp cận trực tiếp .................................................2 3.2.2. Giải pháp 2: Tiếp cận gián tiếp thông qua sàng nguyên tố.....2 3.2.3. Bài tập áp dụng...........................................................................2 3.3. Tổng kết về ước số .............................................................................2 3.4. Bài tập luyện tập................................................................................2 IV. Hiệu quả của sáng kiến.........................................................................2 7.2. Thuyết minh về phạm vi áp dụng sáng kiến ..........................................2 7.2.1. Phạm vi áp dụng sáng kiến...............................................................2 7.2.2. Các bước triển khai áp dụng sáng kiến ...........................................2 7.2.3. Kết quả thu được sau khi áp dụng sáng kiến..................................2 7.3. Thuyết minh về lợi ích kinh tế, xã hội của sáng kiến ............................2
2. DANH MỤC HÌNH ẢNH Hình 1. Thuật toán tìm ước chung lớn nhất ... 2 Hình 2. Code sàng Eratosthenes ...2 Hình 3. Thuật toán 1a tính số ước và tổng các ước . 2 Hình 4. Code thuật toán 1a tính số ước và tổng các ước 2 Hình 5. Thuật toán 1b tính số ước và tổng các ước ..2 Hình 6. Code thuật toán 1b tính số ước và tổng các ước .....2 Hình 7. Code thuật toán 1c tính số ước và tổng các ước .. .... 2 Hình 8. Code thuật toán 1c tính số ước và tổng các ước c . . .. 2 Hình 9. Thuật toán 2 tính số ước và tổng các ước .. .. 2 Hình 10. Code thuật toán 2 tính số ước và tổng các ước ...2 Hình 11. Code sàng các số nguyên tố . 2 Hình 12. Code tính số ước .2 Hình 13. Code tính tổng các ước 2 Hình 14. Thuật toán liệt kê các ước của N .2 Hình 15. Code liệt kê các ước của N 2 Hình 16. Code liệt kê các ước của N gián tiếp 2
3. DANH MỤC KÍ HIỆU Kí hiệu toán học Ý nghĩa [n] Giá trị phần nguyên của n DANH MỤC TỪ VIẾT TẮT Từ viết tắt Ý nghĩa THPT Trung học phổ thông
4. CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM Đôc lâp - Tự do - Hạnh phúc THUYẾT MINH MÔ TẢ GIẢI PHÁP VÀ KẾT QUẢ THỰC HIỆN SÁNG KIẾN 1. Tên sáng kiến: Một số dạng bài toán về ước số và hướng giải quyết trong ôn luyện học sinh giỏi tin học 11 2. Ngày sáng kiến được áp dụng lần đầu: Sáng kiến được áp dụng lần đầu vào ngày 02/10/2021 tại trường THPT Phương Sơn, và được triển khai thực hiện tại trường THPT Cẩm Lý và trường THPT Tứ Sơn huyện Lục Nam, tỉnh Bắc Giang vào ngày 16/10. 3. Các thông tin cần bảo mật (nếu có): Không 4. Mô tả các giải pháp cũ thường làm Giải pháp cũ: Khi dạy các bài tập số học nói chung, các bài tập về ước số nói riêng, thì các bài tập mới chỉ được đưa ra một cách riêng lẻ, không có hệ thống và theo từng dạng bài toán. Thực trạng Năm học 2021-2022 tôi tham gia công tác bồi dưỡng học sinh giỏi tỉnh môn Tin học và bồi dưỡng đội tuyển tin học trẻ. Đối tượng học sinh tôi hướng đến chủ yếu là các em học sinh lớp 11 và lớp 10 (Bồi dưỡng tin học trẻ). Tuy nhiên, dù các em đã được làm quen với ngôn ngữ lập trình từ khi còn học ở trường trung học cơ sở nhưng do quan điểm môn tin là “môn phụ” lại không phải là môn thi chuyển cấp nên các em vẫn chưa thực sự chú tâm học tập nên chất lượng nền (kiến thức cơ sở) có được từ trung học cơ sở dường như là không có, dẫn đến việc khi bồi dưỡng và ôn luyện đội tuyển giáo viên gần như phải dạy lại từ đầu. Trước đây, khi dạy đội tuyển học sinh giỏi cấp tỉnh môn tin học 11, tôi đã đưa ra một số bài tập nói trong tài liệu này tuy nhiên tôi mới chỉ đưa ra một cách riêng lẻ, không có hệ thống và theo từng dạng bài toán. Khi giải quyết các bài toán về ước số nói riêng và các bài tập lập trình 1
5. khác nói chung, học sinh thường chỉ xây dựng thuật toán giải quyết các bộ input có dữ liệu nhỏ dễ nhìn thấy kết quả output và thường không xét đến trường hợp input đặc biệt hay các input có dữ liệu lớn. Bám sát vào cấu trúc của đề thi, tôi ra đề và tự tổ chức cho học sinh khảo sát. Bảng kết quả các lần thi khảo sát đầu năm chất lượng học sinh giỏi chuyên đề ước số (Thang điểm 10) năm học 2021 – 2022 khi chưa thực hiện đề tài: Họ tên Điểm lần 1 Điểm lần 2 Lương Quỳnh Anh 4/10 3/10 Dương Văn Hiếu 4/10 0 Chu Thanh Tùng 4/10 3/10 Qua các lần khảo sát, tôi nhận thấy, hầu hết các thuật toán mà các em học sinh đưa ra chưa giải quyết được các bộ test lớn. Vấn đề đặt ra, là làm thế nào để lấy được điểm với các bộ test có dữ liệu lớn. Muốn vậy cần phải lựa chọn được thuật toán tối ưu và cài đặt được chương trình. Chương trình tối ưu là chương trình giải quyết được những bộ test có dữ liệu lớn, chính xác, độ phức tạp của thuật toán nhỏ, thời gian thực chương trình ngắn... Thời gian thực hiện chương trình không chỉ phụ thuộc vào thuật toán mà còn phụ thuộc vào cấu hình máy tính, kĩ xảo người lập trình, kích thước và tính chất của dữ liệu vào...Để cụ thể và tường minh hơn tôi có sử dụng phần mềm Themis để đo thời gian thực hiện của các chương trình với các bộ test cụ thể (Tối lấy tiêu chí thời gian để chọn thuật toán tối ưu). Các kết quả được tôi thử nghiệm trên máy tính laptop ACER CORE I5, Ram 2GB. Hạn chế của giải pháp Các bài toán về ước số chưa được hệ thống và phân dạng. Chưa xây dựng được thuật toán tối ưu để giải quyết các bài toán. 5. Sự cần thiết phải áp dụng giải pháp sáng kiến: Các bài toán về ước số thường xuyên xuất hiện trong các đề thi, đề thi học sinh giỏi với các bài toán đa dạng và phong phú. Tuy nhiên học sinh khi giải 2
6. quyết bài toán này, các em thường xây dựng thuật toán đơn giản dựa trên định nghĩa hoặc tính chất của bài toán, thuật toán mới chỉ giải quyết được các bộ dữ liệu nhỏ, hoặc nếu giải quyết được các bộ dữ liệu lớn thì không đảm bảo thời gian chạy 1s/test, việc chưa đưa ra được thuật toán tối ưu sẽ làm các em bị mất điểm ở các bộ test lớn. Với mong muốn giúp học sinh giải quyết tốt hơn các bài tập về ước số và hiểu biết sâu sắc hơn cách giải các bài tập này cũng như giúp học sinh tránh bị mất điểm ở các bài toán này, tôi đã nghiên cứu, phân dạng các bài tập liên quan đến ước số để tìm ra nhiều cách làm khác nhau, đánh giá độ phức tạp, đo thời gian thực hiện chương trình, so sánh tìm ra chương trình tối ưu nhất và dễ hiểu nhất. Từ đó nâng cao chất lượng bồi dưỡng học sinh giỏi môn Tin học. 6. Mục đích của giải pháp sáng kiến: Giúp giáo viên: Tổng hợp và chia dạng được các bài toán về ước số, có thêm nguồn tài liệu tham khảo về các thuật toán để giải quyết từng dạng bài. Giúp học sinh: Học sinh nắm chắc và hiểu sâu hơn những kiến thức về ước số, tự tin, không bị lúng túng khi gặp các bài toán liên quan đến ước số. Biết vận dụng linh hoạt các thuật toán cho từng dạng toán, bài toán về ước số, biết lựa chọn và kết hợp các thuật để có được thuật toán tối ưu giải quyết các bài toán về ước số. Có được hệ thống các bài tập luyện tập theo từng dạng bài toán. 7. Nội dung: 7.1. Thuyết minh giải pháp mới I. Các bước tiến hành giải pháp Đối với các bài toán về ước số, tôi chia các bài toán thành hai dạng: Dạng 1: Các bài toán liên quan đến tính số ước, tổng ước của số nguyên. Dạng 2: Các bài toán liên quan đến liệt kê các ước của số nguyên. Với mỗi dạng bài tập, tôi đưa ra hai cách để giải quyết: 3
7. Cách 1: Tiếp cận trực tiếp - giải quyết bài toán dựa vào định nghĩa, tính chất của ước số. Cách 2: Tiếp cận gián tiêp thông qua sàng nguyên tố. Khi tìm hiểu mỗi dạng bài tập tôi tìm hiểu hai nội dung: Nội dung 1: Hướng dẫn học sinh giải một số bài toán điển hình của dạng bài tập đó, tôi sẽ đưa ra hai cách giải, cách 1 là thuật toán các bạn học sinh thường làm, cách này thường bỏ qua một vài trường hợp đặc biệt của bài toán hoặc bị mất điểm ở các bộ test lớn, cách 2 là cách cải tiến tối ưu hơn, giải quyết được bộ test với dữ liệu lớn đảm bảo thời gian chạy 1s/test. Nội dung 2: Đưa ra một số bài tập thuộc dạng bài tập để cho học sinh luyện tập và tự giải. Để minh họa cho các thuật toán trình bày trong biện pháp, tôi sử dụng ngôn ngữ lập trình C++, đồng thời tôi sử dụng phần mềm chấm tự động Themis để đo thời gian thực hiện của các chương trình với các bộ test cụ thể (Tôi lấy tiêu chí thời gian để chọn thuật toán tối ưu). Các bước tôi hướng dẫn học sinh khi giải một bài toán: Bước 1: Xác định bài toán. Bước 2: Suy nghĩ tìm ra ý tưởng. Bước 3: Xây dựng thuật toán. Bước 4: Sử dụng ngôn ngữ lập trình C++ để viết chương trình (trên môi trường Code Block), tính độ phức tạp. Bước 5: Sử dụng phần mềm Themis-chấm bài tự động để chấm cách làm của mình (với các bộ test giáo viên đã xây dựng sẵn, mỗi bộ test cấu hình là 1 điểm, thời gian chạy không quá 1 giây). Bước 6: Cho học sinh trao đổi ý tưởng thuật toán của mình, tìm ra ưu và nhược điểm của thuật toán. Bước 7: Giáo viên định hướng cách làm tối ưu hơn (nếu có). Bước 8: Sử dụng phần mềm Themis để chấm các cách đã viết chương trình. 4
8. Bước 9: Dựa vào kết quả, lựa chọn chương trình có độ phức tạp nhỏ nhất, thời gian thực hiện mỗi test nhỏ nhất và chương trình ngắn gọn dễ hiểu nhất. Bước 10: Lập trình giải các bài tập tương tự với cách đã lựa chọn. Sau đây tôi xin được trình bày nội dung giải pháp: II. Cơ sở lý thuyết 2.1. Ước số ❖ Định nghĩa ước: Số tự nhiên d (d # 0) được gọi là ước của số tự nhiên a khi và chỉ khi a chia hết cho d. Ta nói d là ước của a. Tập các ước của a là U(a)= { d N : d|a} ❖ Tính chất của ước: Số 0 không phải là ước của bất kì số nguyên nào. Số 1 là ước của mọi số nguyên Nếu U(a) = {1,n} thì a là số nguyên tố Nếu dạng phân tích ra thừa số nguyên tố của một số tự nhiên a là: 1 2 = 1 2 Số lượng các ước của a: L(N)= (m1 + 1) * (m2 + 1) * * (mk + 1); Tổng các ước của a: ( 1+1 ― 1) 2+1 ― 1 ( +1 ― 1) ( ) = 1 ∗ 2 ∗ ∗ 1 ― 1 2 ― 1 ― 1 2.2. Ước chung lớn nhất Định nghĩa: Ước chung (UC): Nếu hai tập hợp U(a) và U(b) có những phần tử chung thì những phần tử đó gọi là ước số chung của a và b. Kí hiệu là UC(a; b). Nếu UC(a;b)={1} thì a và b nguyên tố cùng nhau Ước chung lớn nhất (UCLN): Số nguyên dương d được gọi là ước số chung lớn nhất của a và b khi d là phần tử lớn nhất trong tập UC(a;b). Kí hiệu ước chung lớn nhất của a và b là UCLN(a;b) hoặc (a;b) hoặc gcd(a;b). 5
9. ❖ Thuật toán Euclid tìm ước chung lớn nhất: Ý tưởng: Để tìm ước chung lớn nhất của hai số a và b, ta cần thực hiện chia a cho b được thương q và số dư r (r>=0). Khi đó ta có: ế = 0; UCLN(a,b) = 푈 퐿 ( , ) ế #0; Thuật toán: Hình 1. Thuật toán tìm ước chung lớn nhất hai số nguyên dương a và b Code minh họa Hình 2. Code hàm gcd tính ước chung lớn nhất của hai số nguyên dương 2.3. Sàng nguyên tố Eratosthenes Thuật toán: Ghi vào mảng nguyên p tất cả các số nguyên tố từ 1 đến n. Bước 1: Đọc N. Bước 2: Khởi tạo: Mảng p gồm n+1 phần tử, tất cả các phần tử nhận giá trị bằng 0; p[0]=p[1]=1; i=2; 6
10. Bước 3: Nếu i > [ ] chuyển sang bước 7 Bước 4: Nếu p[i]=0 thì Với mọi j có giá trị nhỏ hơn hoặc bằng n là bội của i : p[j]=1; Bước 5: i=i+1; Bước 6: Quay lại bước 3; Bước 7: Ghi nhận kết quả: nếu p[i]=0 thì i là số nguyên tố Code tham khảo: Hình 3. Code sàng Eratosthenes các số nguyên tố nhỏ hơn hoặc bằng N III. Các giải pháp đã tiến hành để giải quyết vấn đề 3.1. Dạng 1: Bài toán liên quan đến số ước và tổng các ước của N. Cho số nguyên dương N ( 1 < N<106). Yêu cầu: 1. Đếm số ước của N 2. Tính tổng các ước của N Dữ liệu vào: UOCSO.INP gồm duy nhất số nguyên dương N Kết quả: UOCSO.OUT Dòng 1: Số lượng ước của N. Dòng 2: Tổng các ước của N. Ví dụ: Gọi số lượng ước của N là d. Tổng các ước của N là S. UOCSO.INP UOCSO.OUT Giải thích 16 120 360 7
11. 3.1.1.Giải pháp 1: Tiếp cận trực tiếp. Thuật toán 1a: Duyệt toàn bộ các số i (i ≥ 1)nhỏ hơn hoặc bằng N để tìm ước của N. Hình 4. Thuật toán 1a tính số ước và tổng các ước của số nguyên N Code tham khảo Hình 5. Code thuật toán 1a tính số ước và tổng các ước của số nguyên N 8
12. Thuật toán 1b: Duyệt toàn bộ các số i (i ≥ 1)nhỏ hơn hoặc bằng phần nguyên của N chia 2 để tìm các ước của N và tính tổng các ước của N. Hình 6. Thuật toán 1b tính số ước và tổng các ước của số nguyên N Code tham khảo Hình 7. Code thuật toán 1b tính số ước và tổng các ước của số nguyên N 9
13. Thuật toán 1c: Duyệt toàn bộ các số i (i ≥ 1)nhỏ hơn hoặc bằng phần nguyên căn bậc hai của N để tìm các ước của N và tính tổng các ước. Hình 8. Thuật toán 1c tính số ước và tổng các ước của số nguyên N Code tham khảo Hình 9. Code thuật toán 1c tính số ước và tổng các ước của số nguyên N 10
14. Thuật toán 2: Sàng ước. Ý tưởng: Duyệt i từ 1 đến [N/2], thêm i vào tổng ước của tất cả các số j - là bội của i. (j có giá trị nhỏ hơn hoặc bằng N) Hình 10. Thuật toán 2 tính số ước và tổng các ước của số nguyên N Code tham khảo Hình 11. Code thuật toán 2 tính số ước và tổng các ước của số nguyên N 11
15. 3.1.2. Giải pháp 2. Tiếp cận gián tiếp thông qua sàng nguyên tố. Ý tưởng: Phân tích N thành tích các thừa số nguyên tố, giả sử N được phân tích thành tích các thừa số nguyên tố có dạng: 1 2 = 1 2 Ta có: Số lượng các ước của N, ta kí hiệu là L(N) được tính theo công thức: L(N)= (m1 + 1) * (m2 + 1) * * (mk + 1); (2.1) Tổng các ước của N, ta kí hiệu là T(N), được tính theo công thức: (2.2) ( 1+1 ― 1) 2+1 ― 1 ( +1 ― 1) ( ) = 1 ∗ 2 ∗ ∗ 1 ― 1 2 ― 1 ― 1 Thuật toán: Bước 1: Sàng các số nguyên tố nhỏ hơn hoặc bằng [ ], ghi vào mảng p, thêm một số nguyên tố vào cuối mảng làm lính canh. Bước 2: Phân tích N ra các thừa số nguyên tố: Với mỗi ước nguyên tố pi của N (p[i]*p[i] <=N): Tính bậc mi của pi (Lưu ý: giá trị của N sẽ được tính lại sau mỗi lần tính bậc). Thừa số pi sẽ có mi +1 ước, ta sẽ nhân dồn kết quả này vào kết quả số ước d của N. 푖+1 Thừa số p i sẽ có tổng các ước là ( 푖 ―1)/(pi – 1), ta sẽ nhân dồn kết quả này vào kết quả tổng ước t của N. Bước 3: Nếu N > 1 (N là số nguyên tố) Số ước số của N: d*=2; Tổng các ước của N: t*=(n+1); Bước 4: Ghi kết quả lên tệp kết quả. Code tham khảo: Sàng nguyên tố 12
16. Hình 12. Code sàng các số nguyên tố nhỏ hơn hoặc bằng N Tính số ước Hình 13. Code tính số ước của số nguyên N 13
17. Tính tổng ước Hình 14. Code tính tổng các ước của số nguyên N theo công thức 2.2 3.1.3. Bài tập áp dụng Bài tập 1: Số phong phú Trong số học, số phong phú có là các số mà tổng các ước số của số đó (không kể chính nó) lớn hơn số đó. Ví dụ, số 12 có tổng các ước số (không kể 12) là 1+2+3+4+6=16>12. Do đó 12 là một số phong phú. Yêu cầu: Hãy đếm xem có bao nhiêu số phong phú trong đoạn [L, R]. Dữ liệu vào: tệp SOPP.INP gồm hai số L, R ( 1≤ L ≤ R≤ 106) Kết quả: Ghi ra tệp SOPP.OUT gồm một số nguyên duy nhất là số số phong phú trong đoạn [L, R]. SOPP.INP SOPP.OUT Giải thích 1 50 9 Từ 1 đến 50 có 9 số phong phú: 12 18 20 24 30 36 40 42 48 14
18. Hướng dẫn giải: Ý tưởng: Do đề bài cho 1≤ L ≤ R≤ 10 6 nên chọn cách tiếp cận trực tiếp để giải quyết bài toán, có thể sử dụng thuật toán 1c hoặc thuật toán 2 để giải quyết: Thuật toán 1c: Viết chương trình sum(n) để tính tổng ước của số nguyên N. Vòng for i dùng để duyệt các giá trị từ L đến R Tính m=sum(i); Nếu m>i thì tăng đếm k++ Thuật toán 2: Dùng sàng ước để tính tổng các ước của các số trong đoạn [L, R] lưu vào mảng tổng ước s. Gọi số lượng số phong phú có trong đoạn [L, R] là d, Khởi tạo d=0; Viết hàm tính tổng các ước của các số từ 1 đến R theo thuật toán 2, lưu tổng các ước của các số từ 1 đến R vào mảng s. for i chạy từ L đến R để duyệt các phần tử của mảng tổng ước s: Nếu s[i]> i, tăng biến đếm d++. Bài tập 2. Tính tổng các ước Cho hai số nguyên dương và (1 ≤ < ≤ 106). Tính tổng tất cả các số nguyên dương thỏa mãn: là ước của 3 là ước của Dữ liệu vào: Cho trong file TongUoc.Inp gồm 2 số nguyên dương và . Kết quả: Ghi ra file TongUoc.Out là tổng tất cả các số nguyên dương thỏa mãn điều kiện trên. Nếu không có giá trị thỏa mãn thì kết quả được xem là 0. Ví dụ: TONGUOC.INP TONGUOC.OUT Giải thích 4 18 3 x=1, x=2 thỏa mãn điều kiện. 1 2 0 Không có x thỏa mãn điều kiện. 15
19. Hướng dẫn giải: Ý tưởng: Từ điều kiện của bài toán: x là ước của a và 3x là ước của b suy ra x là các ước chung của a và b/3: Tìm ước chung lớn nhất của a và b/3: m=gcd(a,b/3); Bài toán trở lại bài toán tính tổng các ước chung trong đoạn từ 1 đến m. Bài tập 3: Số hoàn hảo Số hoàn hảo là số nguyên không âm mà có tổng các ước không kể chính nó bằng chính nó. Ví dụ: n = 6, tổng ước = 1+2+3 = 6 Yêu cầu: Cho số nguyên dương n. Đưa ra số lượng số hoàn hảo nhỏ hơn hoặc bằng n. Dữ liệu vào: HH.INP Một dòng chứa số nguyên dương n (1< n ≤ 109) Dữ liệu ra: HH.OUT Một dòng gồm số lượng các số hoàn hảo nhỏ hơn bằng n, mỗi số cách nhau một dấu cách. Nếu không có số hoàn hảo thì đưa ra 0. Ví dụ HH.INP HH.OUT 30 2 5 0 Hướng dẫn giải: Ý tưởng: Với 1< n ≤ 109, nên chọn cách tiếp cận gián tiếp thông qua sàng nguyên tố để giải quyết bài toán. Viết hàm sum(x) để tính tổng ước của x bằng thuật toán tiếp cận gián tiếp Vòng for i nhận giá trị từ 6 đến N Tính tổng các ước của i: sum(i) Nếu sum(i)=i thì tăng biến đếm lên 1. 3.2. Dạng 2: Liệt kê các ước của N Cho số nguyên dương N (N≤ 109) Yêu cầu: Liệt kê các ước của N. 16
20. Dữ liệu vào: UocN.Inp gồm duy nhất số nguyên dương N Kết quả: UocN.Out gồm các số là ước của N, mỗi số cách nhau một dấu cách. Ví dụ: UocN.Inp UocN.out 100 1 2 4 5 10 20 25 50 100 3.2.1. Giải pháp 1: Tiếp cận trực tiếp Thuật toán: Duyệt toàn bộ các số i (i ≥ 1)nhỏ hơn hoặc bằng phần nguyên căn bậc hai của N để tìm các ước của N. Với mỗi ước i tìm được, ta tìm thêm được 1 ước khác của N là N/i. Lưu các ước vào mảng u. Lưu ý trường hợp phần nguyên căn bậc hai của n bằng căn bậc hai của N (Trường hợp N là số chính phương). Hình 15. Thuật toán liệt kê các ước của N trực tiếp Code tham khảo: 17