Vì sao khi tính số ước và tổng ước của n chỉ cần lặp đến √n?

Locdev
Algorithms
24 Dec, 2022

1. Khái niệm ước của một số

Một số nguyên dương d được gọi là ước của n nếu:

[ n \bmod d = 0 ]

Ví dụ:

Các ước của 12 là: 1, 2, 3, 4, 6, 12

2. Các ước luôn xuất hiện theo cặp

Điểm mấu chốt nằm ở tính chất sau:

Nếu d là ước của n thì n / d cũng là một ước của n.

Ví dụ với n = 36:

Ước thứ nhất	Ước thứ hai
1	36
2	18
3	12
4	9
6	6

👉 Ta thấy các ước luôn đi theo từng cặp nhân với nhau bằng n.

3. Vai trò của căn bậc hai √n

Xét hai ước trong một cặp:

Một số ≤ √n
Một số ≥ √n

Lý do:

Nếu cả hai đều lớn hơn √n → tích sẽ lớn hơn n
Nếu cả hai đều nhỏ hơn √n → tích sẽ nhỏ hơn n

📌 Vì vậy:

Mỗi cặp ước luôn có ít nhất một số ≤ √n

➡️ Khi ta duyệt từ 1 đến √n, ta đã chạm được tất cả các cặp ước.

4. Trường hợp đặc biệt: số chính phương

Nếu n là số chính phương (ví dụ n = 36):

[ \sqrt{36} = 6 ]

Lúc này:

6 × 6 = 36
6 chỉ xuất hiện một lần, không tạo thành cặp khác biệt

👉 Khi lập trình, cần tránh cộng hoặc đếm 6 hai lần.

5. Áp dụng vào tính số ước

Ý tưởng

Duyệt i từ 1 đến √n
Nếu i chia hết n:
- Có ước i
- Có ước n / i
Nếu i == n / i → chỉ tính một lần

Ví dụ

Với n = 36:

i = 1 → (1, 36)
i = 2 → (2, 18)
i = 3 → (3, 12)
i = 4 → (4, 9)
i = 6 → (6)

6. Áp dụng vào tính tổng các ước

Cách làm tương tự:

Mỗi lần tìm được một cặp (i, n/i) thì cộng cả hai vào tổng
Nếu i == n/i thì chỉ cộng một lần

⏱️ Độ phức tạp giảm từ O(n) xuống O(√n) – rất quan trọng khi n lớn.

7. Kết luận

✅ Ta chỉ cần duyệt đến √n vì:

Các ước của n luôn xuất hiện theo cặp
Mỗi cặp có ít nhất một ước ≤ √n
Giúp giảm đáng kể thời gian chạy thuật toán

Đây là một kỹ thuật nền tảng, xuất hiện rất nhiều trong các bài toán số học và lập trình thi đấu.

📌 Gợi ý: Bạn có thể mở rộng ý tưởng này để:

Kiểm tra số nguyên tố
Liệt kê ước số
Tối ưu các bài toán liên quan đến chia hết

Nếu bạn muốn, mình có thể:

Viết thêm code C++ / Python
Hoặc mở rộng thành bài so sánh O(n) vs O(√n)

Chỉ cần nói nhé! 🚀