Liệt kê ước số Viết chương trình nhập vào một số nguyên dương n và in ra tất cả các ước số của n

Câu F44 trang 32 SBT Tin 10: Liệt kê ước số

Viết chương trình nhập vào một số nguyên dương n và in ra tất cả các ước số của n.

Trả lời

Cách 1: Một trong những giải pháp đơn giản là thử mọi giá trị số nguyên d từ l tới n, mỗi khi gặp một giá trị ở là ước số của n thì in ra ngay giá trị d đó. Tham khảo chương trình sau:

Ví dụ:

Cách 2: Cách làm trên khá chậm khi gặp giá trị n lớn (chẳng hạn n = 10⁹). Một cải tiến nhỏ là dựa vào nhận xét: Ngoại trừ ước d = n, tất cả các ước số khác của n đều không vượt quá $\frac{n}{2}$, vì vậy ta chỉ cần thử d trong phạm vi [1, $\frac{n}{2}$] còn riêng ước d = n sẽ được in ra sau. Mặc dù tốc độ chương trình cải thiện gấp đôi, phương pháp này vẫn còn rất chậm.

Cách 3: Dựa vào nhận xét: Nếu d là ước số của n thì “$\frac{n}{d}$ cũng là ước số của n”. Trong hai ước số d và $\frac{n}{d}$, chắc chắn có một số nhỏ hơn hoặc bằng $\sqrt{n}$. Vì thế ta chỉ cần thử d trong phạm vi [1; $\sqrt{n}$], khi tìm thấy. một ước số d của n trong phạm vi này, ta in ra d và in ra luôn cả ước $\frac{n}{d}$

Lưu ý: Trường hợp d = $\frac{n}{d}$ (n là số chính phương), ta chỉ được in ra một ước để tránh trùng lặp.

Tham khảo chương trình sau:

Xem thêm các bài giải SBT Tin học lớp 10 Cánh diều hay, chi tiết khác:

Bài 5: Thực hành viết chương trình đơn giản

Bài 6,7: Câu lệnh rẽ nhánh - Thực hành câu lệnh rẽ nhánh

Bài 8, 9: Câu lệnh lặp thực hành câu lệnh lặp

Bài 10, 11: Chương trình con và thư viện chương trình con có sẵn - Thực hành lập trình với hàm và thư viện

Bài 12, 13: Kiểu dữ liệu xâu kí tự - xử lí xâu kí tự - Thực hành dữ liệu kiểu xâu

Bài 14, 15: Kiểu dữ liệu danh sách - xử lí danh sách - Thực hành với kiểu dữ liệu danh sách