Bộ chia trong python

Viết chương trình Python để tìm tất cả các ước của một số nguyên hoặc số bằng vòng lặp for. Trong ví dụ Python này, vòng lặp for lặp từ 1 đến một số đã cho và kiểm tra xem mỗi số có chia hết cho số không. Nếu Đúng, in số đó dưới dạng ước số

num = int[input["Please enter any integer to find divisors = "]]

print["The Divisors of the Number = "]

for i in range[1, num + 1]:
    if num % i == 0:
        print[i]

Mã Python sau đây thực hiện điều này

Cách tiếp cận này không hiệu quả lắm vì chúng tôi duyệt qua từng số từ 0 đến

def divisors[n]:
    result = []
    for i in range[1, n//2 + 1]:
        if n % i == 0:
            result.append[i]
    result.append[n]
    return result

print[divisors[24]]
# [1, 2, 3, 4, 6, 8, 12, 24]

def divisors[n]:
    result = []
    for i in range[1, n//2 + 1]:
        if n % i == 0:
            result.append[i]
    result.append[n]
    return result

print[divisors[24]]
# [1, 2, 3, 4, 6, 8, 12, 24]

def divisors[n]:
    result = []
    for i in range[1, n//2 + 1]:
        if n % i == 0:
            result.append[i]
    result.append[n]
    return result

print[divisors[24]]
# [1, 2, 3, 4, 6, 8, 12, 24]

độ phức tạp thời gian chạy. Độ phức tạp trong thời gian chạy của việc tính các ước của số n là O[n] khi sử dụng phương pháp này với giả định rằng thao tác modulo có thể được thực hiện trong một bước

Chúng ta có thể làm tốt hơn không?

Phương pháp 2. Giảm số lần lặp lại vòng lặp

Chúng tôi sử dụng hai quan sát để giảm số lần lặp lại của "thuật toán ngây thơ"

Quan sát 1. Nếu số

Please enter any integer to find divisors = 100

1
2
4
5
10
20
25
50
100

Please enter any integer to find divisors = 100

1
2
4
5
10
20
25
50
100

num = int[input["Please enter any integer to find divisors = "]]


i = 1

while[i