Perfect Number

Q: Độ phức tạp thời gian khi kiểm tra một số hoàn hảo là gì?

Việc thu thập các cặp ước đến √n mất thời gian O(√n) và không gian O(1) , khoảng 10^4 bước với n = 10^8 . Việc kiểm tra mọi ứng viên đến n / 2 có độ phức tạp O(n) , khoảng 5 × 10^7 bước với cùng đầu vào.

Q: Có số hoàn hảo lẻ không?

Chưa ai biết. Mọi số hoàn hảo được tìm thấy cho đến nay đều là số chẵn, và các cuộc tìm kiếm đã loại trừ số lẻ nhỏ hơn 10^1500 , nhưng chưa có chứng minh nào cho thấy chúng không thể tồn tại. Hàm của bạn phải hoạt động dựa trên định nghĩa, chứ không phải dựa trên phỏng đoán rằng đầu vào là số chẵn.

Q: Sự khác nhau giữa số hoàn hảo, số phong phú và số khiếm khuyết là gì?

So sánh tổng các ước số thực sự với số đó. Nếu bằng nhau thì số đó là số hoàn hảo, như 28 . Nếu lớn hơn thì số đó là số dư thừa, như 12 , có tổng các ước số bằng 16 . Nếu nhỏ hơn thì số đó là số thiếu, như mọi số nguyên tố, vì ước số thực sự duy nhất của chúng là 1 .

Người mớiToán và mô phỏng

+10

Ước thực sự của n là một ước dương nhỏ hơn chính n. Một số hoàn hảo bằng tổng các ước thực sự của nó: 6 = 1 + 2 + 3. Bạn được cho một số nguyên dương n. Trả về true nếu n là số hoàn hảo và false nếu không phải.

Hàm

isPerfect(n: integer) → boolean

ninteger: số nguyên dương cần kiểm tra
Trả vềboolean: đúng nếu n bằng tổng các ước thực sự của nó, ngược lại là sai

Ràng buộc

1 ≤ n ≤ 10⁸

Ví dụ

Đầu vào: n = 28
Đầu ra: true
Giải thích: Các ước thực sự của 28 là 1, 2, 4, 7 và 14. Tổng của chúng bằng 28, nên 28 là số hoàn hảo.

Đầu vào: n = 12
Đầu ra: false
Giải thích: Các ước số thực sự của 12 là 1, 2, 3, 4 và 6. Tổng của chúng là 16, lớn hơn 12.

Đầu vào: n = 1
Đầu ra: false
Giải thích: 1 không có ước thực sự nào, nên tổng là 0, không phải 1.

Câu hỏi mở rộng

Mọi số hoàn hảo chẵn đều có dạng 2^(p-1) × (2^p-1), trong đó 2^p-1 là số nguyên tố. Bạn có thể liệt kê tất cả các số hoàn hảo nhỏ hơn 10^8 bằng công thức đó mà không cần kiểm tra từng số không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Thử mọi ước số ứng viên đến n / 2 sẽ tốn 5 × 10^7 phép chia khi n = 10^8. Các ước số xuất hiện thành từng cặp có tích bằng n, vì vậy chỉ cần tìm đến √n, khoảng 10^4 bước, rồi cộng cả hai số trong mỗi cặp.

Thêm mọi ước thực sự

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Làm theo định nghĩa: thử từng d từ 1 đến n / 2 và cộng những số chia hết n. Với 28, ta lấy được 1, 2, 4, 7 và 14. Không có ước thực sự nào lớn hơn n / 2, vì khi đó thương sẽ ít nhất là 2. Giới hạn này cũng xử lý được n = 1: vòng lặp chạy không lần nào và tổng vẫn là 0.

Chia đôi khoảng không làm thay đổi tốc độ tăng trưởng. Vòng lặp chạy n / 2 lần với mọi đầu vào, dù đầu vào có phải ước hay không.

Thuật toán

Đặt total thành 0.
Lặp d từ 1 đến n / 2.
Nếu n % d == 0, cộng d vào total.
Trả về kết quả cho biết total == n có đúng hay không.

def isPerfect(n):
    total = 0
    # No proper divisor of n is larger than n / 2.
    for d in range(1, n // 2 + 1):
        if n % d == 0:
            total += d
    return total == n

Thu thập các cặp ước đến căn bậc hai

Ý tưởng

Khi d chia hết cho n, thì n / d cũng vậy: với 28, các cặp là 1 × 28, 2 × 14 và 4 × 7. Một số trong mỗi cặp không lớn hơn √n, vì tích của hai số lớn hơn √n sẽ lớn hơn n. Vì vậy, tìm kiếm đến √n sẽ gặp mỗi cặp đúng một lần, rồi bạn cộng cả hai số.

Cặp 1 × n có cả n, nhưng n không phải là ước thực sự, nên hãy bắt đầu tổng từ 1 và bắt đầu tìm kiếm từ 2. Căn bậc hai ghép cặp với chính nó và chỉ được tính một lần. Viết giới hạn dưới dạng d * d ≤ n để chỉ dùng số nguyên; với n = 10^8, vòng lặp dừng tại d = 10^4.

Thuật toán

Nếu n == 1, trả về false.
Đặt total bằng 1 và d bằng 2.
Trong khi d * d ≤ n: nếu d chia hết n, cộng d vào tổng, đồng thời cộng thêm n / d nếu giá trị này khác d.
Chuyển sang d tiếp theo.
Trả về kết quả kiểm tra total == n.

def isPerfect(n):
    if n == 1:
        return False
    total = 1  # 1 divides every n > 1; n itself does not count
    d = 2
    while d * d <= n:
        if n % d == 0:
            total += d
            partner = n // d
            if partner != d:  # a square root pairs with itself: add it once
                total += partner
        d += 1
    return total == n

Lỗi thường gặp và trường hợp biên

Tính cả chính n thông qua cặp 1 × n. Khi đó, mọi tổng đều lớn hơn n: tổng các ước của 28 là 56.
Gọi 1 là số hoàn hảo. Khi tổng ban đầu là 1, đầu vào 1 thỏa phép so sánh 1 == 1, nhưng tổng các ước thực sự của nó là 0.
Cộng căn bậc hai hai lần. Tổng các ước thực sự của 16 là 15; cộng 4 hai lần sẽ được 19.
Lặp khi d * d < n. Cách này bỏ qua căn bậc hai, nên 4 của 16 không bao giờ được tính.
Lấy giới hạn từ căn bậc hai dấu phẩy động. Ở độ chính xác đơn, căn bậc hai của một số chính phương có thể bị làm tròn xuống thiếu một đơn vị, khiến một ước bị bỏ sót.

Câu hỏi thường gặp3

Độ phức tạp thời gian khi kiểm tra một số hoàn hảo là gì?

Việc thu thập các cặp ước đến √n mất thời gian O(√n) và không gian O(1), khoảng 10^4 bước với n = 10^8. Việc kiểm tra mọi ứng viên đến n / 2 có độ phức tạp O(n), khoảng 5 × 10^7 bước với cùng đầu vào.

Có số hoàn hảo lẻ không?

Chưa ai biết. Mọi số hoàn hảo được tìm thấy cho đến nay đều là số chẵn, và các cuộc tìm kiếm đã loại trừ số lẻ nhỏ hơn 10^1500, nhưng chưa có chứng minh nào cho thấy chúng không thể tồn tại. Hàm của bạn phải hoạt động dựa trên định nghĩa, chứ không phải dựa trên phỏng đoán rằng đầu vào là số chẵn.

Sự khác nhau giữa số hoàn hảo, số phong phú và số khiếm khuyết là gì?

So sánh tổng các ước số thực sự với số đó. Nếu bằng nhau thì số đó là số hoàn hảo, như 28. Nếu lớn hơn thì số đó là số dư thừa, như 12, có tổng các ước số bằng 16. Nếu nhỏ hơn thì số đó là số thiếu, như mọi số nguyên tố, vì ước số thực sự duy nhất của chúng là 1.

def isPerfect(n):
    # Viết code tại đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

n = 28

Đầu ra mong đợi

true