Ý tưởng

Đếm ước bằng cách duyệt ~i~ từ ~1~ đến ~\sqrt n~. Nếu ~i~ chia hết ~n~, ta có một hoặc hai ước tương ứng ~i~ và ~n/i~. Để tìm ước nguyên tố lớn nhất, phân tích ~n~ ra thừa số nguyên tố bằng phép chia thử và lưu thừa số cuối cùng gặp được.

Độ phức tạp

~O(\sqrt n)~.