Tài liệu tham khảo về ước số, bội số trong lập trình
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (85.86 KB, 1 trang )
Ước số, bội số
1. Số các ước của một số
Giả sử N được phân tích thành thừa số nguyên tố như sau:
N a i b j ... c k (VD: 18 2 3 2 )
Ước số của N có dạng: a x b y ... c z trong đó
0 x i,0 y j ,...,0 z k
Suy ra, số các ước của N là (i 1) ( j 1) ... (k 1)
Ví dụ:
N = 100 = 2 2 5 2 , số ước số của 100 là (2+1)(2+1) = 9 (các ước là: 1, 2, 4, 5, 20, 20, 25,
50, 100).
N = 24 = 2 3 3 , số ước số của 24 là (3+1)(1+1) = 8 (các ước số là: 1, 2, 3, 4, 6, 8, 12, 24).
2. Tống các ước của một số
N a i b j ... c k
Tổng ước của N là :
(a i 1 1) (b j 1 1)
(c k 1 1)
S
...
a 1
b 1
c 1
Ví dụ:
Tổng các ước của N = 24 là:
(2 31 1) (311 1)
60
2 1
3 1
