Số bạn bè và số hoàn hảo

Số bè bạn và số hoàn hảo

Trong quá trình học lập trình và thuật toán, đa số trong chúng ta đã từng nghe tới và làm các bài tập về các số bè bạn (friend numbers) và số hoàn hảo (perfect numbers). Các số bè bạn n, m là hai số nguyên mà tổng ước số của n bằng m và tổng các ước của m bằng n, ví dụ như cặp số bè bạn nhỏ nhất là 220 và 284. Các số hoàn hảo là các số mà tổng các ước thực sự của nó bằng chính nó, ví dụ như các số hoàn thiện đầu tiên là 6, 28 ...
Bài toán thường liên quan tới các số bè bạn và số hoàn hảo là in ra tất cả các cặp số bè bạn và các số hoàn hảo không vượt quá một số nguyên N nào đó. Đây là hai bài toán khác nhau song lại có liên quan mật thiết với nhau vì trong quá trình xây dựng giải thuật cho bài toán chúng ta đều cần đến khái niệm gọi là tổng các ước của một số nguyên. Trong trường hợp N là một số nguyên nhỏ (N < 10000) thì một thuật toán đơn giản và hết sức trực quan cũng tạm chấp nhận được là:
• Xây dựng một hàm tính tổng ước của một số nguyên
• Duyệt các số từ 2 tới N, nếu tồn tại hai số i, j khác nhau mà tổng ước của i bằng j và tổng ước của j bằng i thì in ra i, j. Khi đó i, j chính là một cặp số bè bạn.
• Duyệt các số từ 2 tới N, nếu tổng ước của số đó bằng chính nó thì in ra màn hình, đó chính là một số hoàn thiện cần tìm.
Trước hết ta đi xây dựng hàm tính tổng các ước số của một số nguyên m: ta đã biết các ước số của m, nếu có sẽ không vượt quá căn bậc 2 của m (tức là sqrt(m)), và khi a là một ước của m thì m/a (m chia a) cũng là một ước của m (phần này xin đọc thêm bài báo “Số nguyên tố” để biết thêm chi tiết) nên một thuật toán hiệu quả sẽ xét các ứng cử viên có thể là ước của m nằm trong khoảng 1 tới sqrt(m) (gọi ước này là a), sau đó cộng a và m/a vào tổng ước của số m. Cài đặt cụ thể bằng ngôn ngữ C của thuật toán như sau:


Sau khi đã có hàm tính tổng ước số của một số nguyên, việc in ra các số hoàn thiện trở nên dễ dàng với 1 vòng lặp, nên ta chỉ xét đoạn chương trình in ra các cặp số hoàn thiện phân biệt (không kể thứ tự của các số):


Hầu hết các lập trình viên mới học lập trình và thuật toán sẽ dừng lại ở đây. Thuật toán in ra các cặp số bè bạn có hai vòng lặp lồng nhau, thuật toán sẽ chạy cỡ khoảng O(N) = N*(N+1)/2 bước, mỗi bước gọi tới hàm tong_uocso() hai lần để thực hiện so sánh nên độ phức tạp của thuật toán sẽ là O(N) = N2 * O(hàm tong_uocso()). Nếu N = 1000000 thì chắc chắn thuật toán không thể chạy trong thời gian 3 giây (thời gian test tối đa của các bài toán trong các cuộc thi lập trình).
Tuy nhiên quan sát kỹ thuật toán, ta thấy rằng mỗi lần xét i trong vòng lặp thứ nhất, ta không cần thiết phải chạy một vòng lặp để xét các ứng cử viên có thể làm thành một cặp số bè bạn với i, mà chỉ cần xét số z = tong_uocso(i). Vì vậy một thuật toán hiệu quả hơn nhiều sẽ là như sau:


Ta cần thêm điều kiện z > i để in ra các cặp số khác nhau (vì z bây giờ đóng vai trò thay j trong thuật toán trước).
Rõ ràng thuật toán thứ hai này có độ phức tạp nhỏ hơn nhiều so với thuật toán thứ nhất, thay vì chạy hai vòng lặp, ta chỉ cần một vòng lặp là đủ. Tất nhiên cải tiến này không thể áp dụng cho bài toán số hoàn hảo vì ta cũng chỉ cần một vòng lặp để in ra tất cả các số hoàn hảo không vượt quá N.
Rõ ràng bây giờ các cải tiến của chúng ta, nếu có, sẽ không thể tập trung vào các vòng lặp, mà chỉ có thể nằm ở việc tính tổng ước số của mỗi số nguyên.
Chúng ta đã biết thuật toán sàng Erastosthene để đánh dấu các số nguyên không phải là số nguyên tố (các số còn lại không được đánh dấu sẽ là số nguyên tố - có thể tham khảo trong bài báo số nguyên tố). Thuật toán sàng Erastosthene dựa trên một chi tiết hết sức tinh tế sau: nếu z là một số nguyên tố (hay hợp số) thì các bội số của z sẽ là các hợp số. Chúng ta hoàn toàn