Câu hỏi:

13/07/2024 3,835

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.

Quảng cáo

Trả lời:

verified
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 = 109). 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 = nd (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)

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

Lời giải

Tương tự như bài F35, có thể có nhiều cách viết vòng lặp. Số nguyên dương chẵn lớn nhất không vượt quá n là hiệu của n với số dư của phép chia n cho 2. Số nguyên dương chẵn nhỏ nhất là số 2.

Cách 1: Sử dụng vòng lặp whi1e: Khởi tạo x = n -n % 2 cho đến khi x > 0 ta in ra x sau đó giảm x đi 2 đơn vị. Tham khảo chương trình sau:

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

Cách 2: Sử dụng vòng lặp for. Tham khảo chương trình sau:

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

Cách 3: Ta cũng có thể sử dụng vòng lặp for nhưng sửa lại khai báo range để mỗi bước giá trị số in ra được giảm đi 2 đơn vị. Tham khảo chương trình sau:

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

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP