Phân tích thừa số để đếm và tìm các ước

Lan có 84 tấm thẻ và muốn chia thành các nhóm bằng nhau, không thừa thẻ. Bạn ấy cần biết có bao nhiêu kích thước nhóm khác nhau. Nếu kiểm tra từng số từ 1 đến 84, Lan sẽ tìm được đáp án, nhưng cách đó khó dùng khi số thẻ lớn hơn nhiều. Phân tích 84 thành các thừa số nguyên tố giúp đếm mọi cách mà không bỏ sót.

Mỗi số lớn hơn một được tạo từ các thừa số nguyên tố

Một ước dương (positive divisor) của n là số nguyên dương chia hết n. Chẳng hạn, 3 là ước của 12 vì 12 % 3 == 0. Số 5 không phải ước của 12. Số 1 có đúng một ước dương là chính nó.

Một thừa số nguyên tố (prime factor) vừa là ước của số đang xét, vừa là số nguyên tố. Khi một thừa số xuất hiện nhiều lần, ta ghi số lần đó bằng số mũ (exponent). Ví dụ, 84 bằng 2 * 2 * 3 * 7, hay 2² * 3 * 7. Các cặp (2, 2), (3, 1), (7, 1) ghi đủ thông tin này.

Mỗi số nguyên lớn hơn 1 có duy nhất một cách phân tích thành tích các số nguyên tố, nếu không kể thứ tự. Số 1 có phân tích rỗng: không có thừa số nguyên tố nào. Quy ước tích rỗng bằng 1 sẽ giúp các công thức sau xử lý số này tự nhiên.

factors = [(2, 2), (3, 1), (7, 1)]
product = 1
for p, e in factors:
    product *= p ** e
print(product)

84

Tích thu được bằng 84. Mỗi cặp đóng góp một lũy thừa; số mũ cho biết phải nhân thừa số đó bao nhiêu lần.

Thử chia và cập nhật phần còn lại

Ta thử các số d từ 2 trở lên. Khi d chia hết phần còn lại, ta chia liên tiếp cho đến khi không chia được nữa. Số lần chia chính là số mũ của d. Sau đó chuyển sang d tiếp theo.

Hình dưới đây cho thấy phần còn lại thay đổi thế nào với 84. Bước cuối giữ 7 vì không còn ước nào cần thử đến căn bậc hai của nó.

Chương trình sau tự phân tích số được nhập. Biến rest là phần chưa tách, không phải giá trị ban đầu.

84

rest = int(input())
d = 2
factors = []
while d * d <= rest:
    if rest % d == 0:
        e = 0
        while rest % d == 0:
            rest //= d
            e += 1
        factors.append((d, e))
    d += 1
if rest > 1:
    factors.append((rest, 1))
print(factors)

[(2, 2), (3, 1), (7, 1)]

Sau khi chia hết cho 2 và 3, phần còn lại là 7. Điều kiện d * d <= rest không còn đúng, nên vòng lặp dừng. Nếu quên thêm phần còn lại, kết quả sẽ thiếu 7. Với đầu vào 1, danh sách kết quả rỗng.

Vì sao được phép dừng? Nếu rest hợp số, nó có một ước nguyên tố không lớn hơn căn bậc hai của chính nó. Ước ấy đã được thử trước khi điều kiện dừng xảy ra. Do đó phần còn lại lớn hơn 1 phải là số nguyên tố.

Một ước hợp số không thể được ghi nhầm thành thừa số. Mọi ước nguyên tố nhỏ hơn của nó đã được loại hết trước đó. Trong trường hợp xấu nhất, ta thử không quá khoảng căn bậc hai của số ban đầu. Với n <= 10^12, số lần thử vào cỡ một triệu, tức O(sqrt(n)) thời gian và O(log n) chỗ lưu các cặp.

Mỗi ước tương ứng với một lựa chọn số mũ

Xét 360 = 2³ * 3² * 5. Để tạo một ước dương của 360, số mũ của 2 chỉ có thể là 0, 1, 2 hoặc 3. Số mũ của 3 có ba lựa chọn, còn số mũ của 5 có hai lựa chọn. Các lựa chọn độc lập, nên có 4 * 3 * 2 = 24 ước.

Hình chọn 4 * 3 * 5 = 60. Mọi ước đều xuất hiện đúng một lần vì phân tích nguyên tố là duy nhất. Không được chọn 2⁴, vì 360 chỉ chứa ba thừa số 2.

Nếu n = p₁^a₁ * ... * pₖ^aₖ, số ước dương là tích (a₁ + 1) * ... * (aₖ + 1). Số 1 không có cặp nào, nên tích rỗng cho kết quả 1. Đoạn sau tính số ước của 360 từ phân tích đã biết.

factors = [(2, 3), (3, 2), (5, 1)]
count = 1
for p, e in factors:
    count *= e + 1
print(count)

24

Chỉ nhân các số mũ là sai, vì bỏ mất lựa chọn số mũ 0. Trong ví dụ, chọn số mũ 0 của cả ba nguyên tố tạo ra ước 1. Sau khi phân tích, phép nhân cần O(k) bước với k thừa số nguyên tố phân biệt.

Tổng các ước là tích của các tổng lũy thừa

Để cộng mọi ước, ta cộng các lựa chọn của từng nguyên tố rồi nhân các tổng ấy. Với 360, biểu thức là (1 + 2 + 4 + 8) * (1 + 3 + 9) * (1 + 5). Khi khai triển, mỗi tích chọn đúng một số từ mỗi ngoặc. Vì thế mỗi ước xuất hiện một lần, không thừa và không thiếu.

factors = [(2, 3), (3, 2), (5, 1)]
total = 1
for p, e in factors:
    power = 1
    group = 0
    for _ in range(e + 1):
        group += power
        power *= p
    total *= group
print(total)

1170

Tổng thu được là 1170. Với số 1, không có nhóm nào để nhân và giá trị ban đầu là 1. Phép cộng lặp tránh lỗi chia khi áp dụng công thức tổng cấp số nhân dưới phép lấy dư. Nếu đề yêu cầu lấy dư, áp dụng quy tắc nhân và cộng ở Bài 7.

Với từng cặp (p, e), ta thực hiện e + 1 bước. Tổng số bước sau phân tích là O(log n), vì mỗi thừa số nguyên tố ít nhất bằng 2. Bộ nhớ phụ ngoài danh sách phân tích là O(1).

Số chính phương có mọi số mũ chẵn

Một số chính phương (perfect square) là bình phương của một số nguyên. Khi bình phương một tích, mỗi số mũ đều được nhân đôi. Vì vậy mọi số mũ trong phân tích của số chính phương đều chẵn. Chiều ngược lại cũng đúng: chia đôi từng số mũ sẽ cho căn nguyên của số đó.

examples = {36: [(2, 2), (3, 2)], 72: [(2, 3), (3, 2)]}
for n, factors in examples.items():
    print(n, all(e % 2 == 0 for p, e in factors))

36 True
72 False

Số 36 đạt điều kiện vì cả hai số mũ đều chẵn. Số 72 không đạt vì số mũ của 2 là 3. Số 1 cũng là chính phương: 1 * 1 = 1, và không có số mũ lẻ nào. Nếu chỉ cần kiểm tra một số, math.isqrt thường đơn giản hơn phân tích thừa số.

from math import isqrt
for n in (1, 36, 72, 10**12):
    root = isqrt(n)
    print(n, root * root == n)

1 True
36 True
72 False
1000000000000 True

isqrt trả phần nguyên của căn bậc hai, nên phép so sánh dùng hoàn toàn số nguyên. Không nên dựa vào so sánh số thực để kiểm tra số lớn.

Sinh ước bằng cách mở rộng danh sách

Khi cần liệt kê, bắt đầu với danh sách chỉ có 1. Với mỗi cặp (p, e), lấy bản sao các ước đã có. Nhân từng ước trong bản sao với p, p², đến p^e, rồi thêm vào danh sách.

factors = [(2, 2), (3, 1), (7, 1)]
divisors = [1]
for p, e in factors:
    previous = divisors[:]
    power = 1
    for _ in range(e):
        power *= p
        for value in previous:
            divisors.append(value * power)
divisors.sort()
print(divisors)

[1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42, 84]

Sau khi xử lý một nguyên tố, danh sách chứa đúng mọi tích hợp lệ từ các nguyên tố đã xử lý. Bản sao ngăn các phần tử vừa thêm bị dùng lại trong cùng lượt. Nếu duyệt trực tiếp danh sách đang nối thêm, chương trình có thể sinh sai hoặc không dừng.

Số phần tử cuối cùng là D, số ước của n. Tạo danh sách cần O(D * k) bước theo cách cài đặt này; sắp xếp cần O(D log D). Bộ nhớ là O(D). Nếu đề chỉ hỏi số lượng hoặc tổng, công thức tiết kiệm việc lưu và sắp xếp.

Sàng ước nguyên tố nhỏ nhất cho nhiều truy vấn

Giả sử có hàng nghìn số trong khoảng từ 1 đến một triệu. Thử chia từng số nguyên tố gần một triệu có thể lặp lại gần một nghìn phép thử cho mỗi truy vấn. Ta chuẩn bị bảng một lần rồi dùng lại.

Ước nguyên tố nhỏ nhất (smallest prime factor, viết tắt SPF) của x > 1 là nguyên tố nhỏ nhất chia hết x. Bảng spf lưu ước đó ở vị trí x. Với số nguyên tố p, giá trị spf[p] chính là p. Không cần tra spf[1].

limit = 100
spf = list(range(limit + 1))
for p in range(2, limit + 1):
    if spf[p] == p and p * p <= limit:
        for x in range(p * p, limit + 1, p):
            if spf[x] == x:
                spf[x] = p
for value in (84, 97, 1):
    x = value
    factors = []
    while x > 1:
        p = spf[x]
        e = 0
        while x % p == 0:
            x //= p
            e += 1
        factors.append((p, e))
    print(value, factors)

84 [(2, 2), (3, 1), (7, 1)]
97 [(97, 1)]
1 []

Khi xét một nguyên tố p, chỉ ghi vào vị trí chưa có ước nhỏ hơn. Các bội dưới p * p đã có một ước nguyên tố nhỏ hơn p. Nhờ đó giá trị được ghi đầu tiên là ước nguyên tố nhỏ nhất. Giá trị 97 tự trỏ tới nó, còn 1 cho danh sách rỗng.

Mỗi lần tra bảng, chia phần còn lại cho ước được lưu. Với 84, các phép chia lần lượt dùng 2, 2, 3 và 7. Mỗi phép chia giảm số ít nhất một nửa, nên một truy vấn cần tối đa O(log x) phép chia.

Sàng kiểu này tốn O(N log log N) thời gian và O(N) bộ nhớ. Với N = 10^6 và q = 10^4, tổng thời gian lý thuyết là O(N log log N + q log N). Bảng chỉ trả lời được số không vượt N. Chi phí tạo bảng không đáng nếu chỉ có một truy vấn nhỏ.

Chọn cách làm và đối chiếu kết quả

Khi kiểm tra chương trình phân tích, đừng chỉ nhìn một ví dụ thuận lợi. Số 1, một số nguyên tố, một bình phương và một tích nhiều nguyên tố cho biết các nhánh khác nhau có hoạt động hay không. Với dữ liệu nhỏ, ta còn có thể duyệt mọi số từ 1 đến n để kiểm tra công thức.

Đoạn sau so sánh hai cách tính số lượng và tổng ước của các số từ 1 đến 100. Cách thứ nhất dựa trên thử chia. Cách thứ hai kiểm tra trực tiếp từng ứng viên. Cách thứ hai chậm khi n lớn, nhưng đơn giản và phù hợp làm phép đối chiếu nhỏ.

def by_factors(n):
    rest = n
    d = 2
    count = total = 1
    while d * d <= rest:
        if rest % d == 0:
            e = 0
            power = group = 1
            while rest % d == 0:
                rest //= d
                e += 1
                power *= d
                group += power
            count *= e + 1
            total *= group
        d += 1
    if rest > 1:
        count *= 2
        total *= 1 + rest
    return count, total

for n in range(1, 101):
    divisors = [d for d in range(1, n + 1) if n % d == 0]
    assert by_factors(n) == (len(divisors), sum(divisors))
print("Đã khớp 100 số")

Đã khớp 100 số

Lệnh assert gây lỗi nếu hai kết quả khác nhau. Khi chương trình in được dòng cuối, cả 100 số trong phạm vi đã thử đều khớp. Điều này giúp tìm lỗi, nhưng không thay thế lập luận cho mọi số hợp lệ. Một bộ kiểm tốt cần cả các giá trị lớn và giới hạn của đề.

360

rest = int(input())
factors = []
d = 2
while d * d <= rest:
    if rest % d == 0:
        e = 0
        while rest % d == 0:
            rest //= d
            e += 1
        factors.append((d, e))
    d += 1
if rest > 1:
    factors.append((rest, 1))
count = total = 1
for p, e in factors:
    count *= e + 1
    power = group = 1
    for _ in range(e):
        power *= p
        group += power
    total *= group
print(count, total)

24 1170

Đầu vào 360 cho số lượng 24 và tổng 1170. Nếu đổi đầu vào thành 1, cả hai kết quả đều là 1. Hãy thử thêm số nguyên tố và một lũy thừa nguyên tố để kiểm tra hai nhánh quan trọng.

Lỗi thường gặp

Tóm tắt

• Thử chia tách từng số mũ và giữ phần nguyên tố còn lại sau vòng lặp.
• Mỗi ước tương ứng duy nhất với một lựa chọn số mũ hợp lệ.
• Số lượng ước là tích các e + 1; tổng ước là tích các tổng lũy thừa.
• Một số chính phương có mọi số mũ chẵn; số 1 là trường hợp phân tích rỗng.
• SPF dùng bộ nhớ O(N) để tăng tốc nhiều truy vấn trong cùng miền.

Kiểm tra nhanh

Đọc thêm

• Tài liệu Python về số nguyên và phép chia.
• Tài liệu Python về math.isqrt.