Tính tổng các ước của n số nhập vào từ bàn phím

[rogp10]

Giờ em ví dụ số 12. Nếu chạy đến sqrt(12) thì sẽ chỉ chạy đến 3,3. Thiếu mất ước bằng 6 anh ạ

Một lần bạn lấy được cả hai số nhé, không sót đâu. 2*6 = 12 thì bạn lấy được cả số 6 rồi còn gì.

Bạn đưa về bài toán phân tích số n thành tích các số nguyên tố. Giả sử số n phân tích thành tích của m số nguyên tố. Thì output sẽ bằng 2 mũ m.

Áp dụng quy nạp trên số thừa số nguyên tố cũng đc.

Để tránh phải dùng tính chất UFD của N* ta c/m từ một u | mn sẽ phân tích được u = dd’ (d | m && d’ | n) duy nhất.
Đầu tiên ta c/m gcd(d, d’) = 1 với mọi (d, d’) thỏa mãn. Giả sử điều ngược lại, vậy gcd(d, d’) chia hết cả m và n, dẫn đến mâu thuẫn. Sau đó đặt d1, d’1 tương ứng sao cho dd’ = d1d’1 (hay d/d’1 = d1/d’), nhưng hai phân số này đều tối giản, suy ra đpcm.

Vậy Sigma(d|m) d * Sigma(d’|n) d’ = Sigma(dd’ | mn) dd’ (do (d, d’) -> dd’ là một-một), hay Sigma(m)Sigma(n) = Sigma(mn).