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.

Bạn cần đăng nhập để báo cáo vi phạm tài liệu

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.

Nguyễn Lê Khánh Vy Ngày: 26-03-2023 Lớp 10

369

Với Giải Câu F44 trang 32 SBT Tin học 10 Cánh diều trong Bài 8, 9: Câu lệnh lặp. Thực hành câu lệnh lặp Sách bài tập Tin học 10 Cánh diều hay nhất, chi tiết sẽ giúp học sinh dễ dàng làm bài tập trong SBT Tin học 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.

Câu F44 trang 32 SBT Tin học 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.

Lời giả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:

(ảnh 12)

Ví dụ

Input	Output
60	1 2 3 4 5 6 10 12 15 20 30 60

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{�}{2}$ , vì vậy ta chỉ cần thử d trong phạm vi [1, $\frac{�}{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{�}{�}$ cũng là ước số của n”. Trong hai ước số d và $\frac{�}{�}$ , chắc chắn có một số nhỏ hơn hoặc bằng $\sqrt{�}$ . Vì thế ta chỉ cần thử d trong phạm vi [1; $\sqrt{�}$ ], 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{�}{�}$