Danh mục: 25 Học Python – Tính tổng những số chia hết cho 3 hoặc 5 mới nhất

Bài 25:  Đếm Số Ước Của Số Nguyên n Bằng Python

Giới Thiệu

Trong toán học, một ước của số nguyên n là một số nguyên chia hết n mà không để lại dư. Bài toán đếm số lượng ước số của một số nguyên n có nhiều ứng dụng trong lý thuyết số và lập trình. Bài viết này sẽ hướng dẫn cách đếm số ước của một số nguyên bằng Python một cách tối ưu.

Ưu Đãi lớn thêm danh sách 10 bài tập python  rèn luyện kỹ năng và nâng cao tay nghề:

1. Bài 21: Tìm Những Số Chia Hết Cho 3 bằng Python mới nhất
2. Bài 22: Đếm Số Lượng Số Chia Hết Cho 3 Bằng Python
3. Bài 23 : Tính Tổng Những Số Chẵn Bằng Python
4. Bài 24 Tính Tổng Những Số Chia Hết Cho 3 Hoặc 5 Bằng Python
5. Bài 25:  Đếm Số Ước Của Số Nguyên n Bằng Python
6. Bài 26 – Tính Tổng Những Số Chia Hết Cho 3 và 5 bằng Python

7. Bài 27: Kiểm tra số nguyên tố bằng Python (2 cách tối ưu)

8. Bài 28: Tính Tổng Các Số Nguyên Từ m Đến n Bằng Python
9. Bài 29: Đếm Số Chia Hết Cho 3 Từ m Đến n Bằng Python
10. Bài 30 Đếm Số Chia Hết Cho 3 Hoặc 5 Và Tính Tổng Các Số Chẵn Bằng Python

Cách Xác Định Số Ước

Một số d được coi là ước của n nếu thỏa mãn điều kiện:

• n % d == 0 (tức là n chia hết cho d).

Viết Chương Trình Python

Chương trình dưới đây sẽ đếm số lượng ước của một số nguyên n.

# Hàm đếm số ước của số nguyên n
def dem_uoc(n):
    dem = 0
    for i in range(1, n + 1):
        if n % i == 0:
            dem += 1
    return dem
# Nhập số nguyên từ người dùng
n = int(input("Nhập số nguyên n: "))
print(f"Số lượng ước của {n} là: {dem_uoc(n)}")

Giải Thích Chương Trình

• Duyệt qua các số từ 1 đến n: Kiểm tra từng số xem có phải là ước của n không.
• Kiểm tra điều kiện chia hết: Nếu n % i == 0, tăng biến đếm dem.
• Trả về số lượng ước: Hiển thị kết quả sau khi kiểm tra hết các số.

Tối Ưu Chương Trình

Cách trên có độ phức tạp O(n), có thể được tối ưu thành O(√n) bằng cách chỉ duyệt đến √n:

# Hàm tối ưu đếm số ước

def dem_uoc_toi_uu(n):

    dem = 0

    for i in range(1, int(n**0.5) + 1):

        if n % i == 0:

            dem += 1

            if i != n // i:

                dem += 1

    return dem

# Nhập số nguyên từ người dùng

n = int(input("Nhập số nguyên n: "))

print(f"Số lượng ước của {n} là: {dem_uoc_toi_uu(n)}")

Giải Thích Tối Ưu

• Duyệt chỉ đến √n: Vì nếu i là ước của n, thì n // i cũng là ước của n.
• Kiểm tra cặp ước: Nếu i khác n // i, ta đếm thêm một ước.
• Cải thiện tốc độ: Giảm số lần lặp giúp chương trình chạy nhanh hơn.

Ứng Dụng

• Kiểm tra số nguyên tố (nếu n chỉ có 2 ước là 1 và chính nó).
• Ứng dụng trong các bài toán tìm bội chung, ước chung.
• Xây dựng các thuật toán trong lý thuyết số.

Kết Luận

Bài toán đếm số ước của một số nguyên có thể được giải quyết dễ dàng bằng Python. Sử dụng thuật toán tối ưu giúp giảm thời gian xử lý đáng kể, đặc biệt với các số lớn.

Nếu bạn thấy hay ! xin bạn 1 phút ! vui lòng đánh giá 5 sao cho trang website của chúng tôi ! để có động lực làm thêm nhiều bài hay nữa ! cảm ơn quý khách nhé !

Khóa học Python online từ cơ bản đến nâng cao