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 hỏi trong đề: Giải SBT Tin 10 Bài 8, 9: Câu lệnh lặp có đáp án !!

Quảng cáo

Trả lời:

Giải bởi Vietjack

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:

Liệt kê ước số Viết chương trình nhập vào một số nguyên dương n (ảnh 1)

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{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:

Liệt kê ước số Viết chương trình nhập vào một số nguyên dương n (ảnh 2)

Hot: 1000+ Đề thi giữa kì 2 file word cấu trúc mới 2026 Toán, Văn, Anh... lớp 1-12 (chỉ từ 60k). Tải ngay

Sách thầy cô Vietjack biên soạn:

Xem thêm »

CÂU HỎI HOT CÙNG CHỦ ĐỀ

Câu 1

In ra tổng các số chia hết cho 3 hoặc chia hết cho 5

Với n nhập từ bàn phím, viết chương trình đưa ra màn hình tổng các số tự nhiên nhỏ hơn n và chia hết cho 3 hoặc chia hết cho 5.

Xem đáp án

Lời giải

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

In ra tổng các số chia hết cho 3 hoặc chia hết cho 5 Với n nhập từ bàn phím, viết (ảnh 1)

Câu 2

In ra các số lẻ

Viết chương trình nhập vào số nguyên n và in ra các số nguyên dương lẻ không lớn hơn n theo thứ tự tăng dần.

Xem đáp án

Lời giải

Bài này có thể có nhiều cách viết vòng lặp.

Cách 1: Sử dụng vòng lặp while: Khởi tạo x = 1 là số nguyên dương lẻ nhỏ nhất, cho đến khi x ≤ n ta in ra x sau đó tăng x lên 2 đơn vị. Tham khảo chương trình sau:

In ra các số lẻ Viết chương trình nhập vào số nguyên n và in ra các số nguyên dương (ảnh 1)

Cách 2: Sử dụng vòng lặp for: Dãy số lẻ cần in ra là 0 × 2 + 1, 1 × 2 + 1, 2 × 2 + 1, ..., k × 2+ 1, trong đó k là giá trị số nguyên lớn nhất thoả mãn: k × 2 + 1≤ n, tức là $k = [\frac{n - 1}{2}]$ . Tham khảo chương trình sau: