Em đang thắc mắc cái thuật toán tìm tổng các ước của một số trong mảng 1 chiều. Rồi tìm ra tổng ước của số nào là lớn nhất. Ai chỉ giúp em không ạ?
Bài toán tìm tổng các ước
Bác thử tìm tất cả các ước của số đó rồi cộng lại xem. Tìm tất cả các ước thì đơn giản nhất là lấy số x đó chia cho từng số một từ 2 đến (x-1), vì 1 và x cũng chính là ước của số x luôn. Cái đó thì mất nhiều thời gian, hiệu quả hơn là chỉ lấy x chia cho từ 2 đến căn của x (sqrt(x)), nếu số nào có số dư là 0 thì là ước. Mà ước thì đi kèm là 2 số nếu tìm đc ước a thì lấy x/a=b thì ra ước thứ 2. Tại sao lại chỉ lấy x chia cho từ 2 đến sqrt(x) là vì ví dụ sqrt(20) = 4.47. Nếu a*b=x thì a và b không thể đồng thời cùng lớn hơn 4 được. Chỉ có thể 1 số <= 4 số còn lại >4 thôi. Vì vậy nếu tìm đc 1 ước trong khoảng 2 đến 4 thì tìm lại đc số còn lại. Nó còn có bài toán tìm số lượng ước của 1 số nhg lâu rồi không động tới 
. Tìm đc tổng xong rồi thì lại dùng bài sắp xếp dãy số để tìm số lớn nhất
1 Like
Sẵn làm clip luôn 
2 Likes
cảm ơn anh rất nhiều
Nếu n lớn cỡ 10^18 thì phải dùng thuật toán để phân tích ra thừa số nguyên tố (có thể tham khảo thuật toán pollar-rho)
nếu n cỡ 10^12 thì sàng các số nguyên tố đến 10^6 rồi dùng số đó để chia lần lượt các số tìm dc
3 Likes
Có cách nào để tìm ra số có tổng ước lớn nhất trông khoảng 10^8 mà không dùng sàng nguyên tố không bác. bởi dùng sàng nguyên tố thì lại phải dùng tới mảng, như vậy sẽ tốn bộ nhớ.
bác giúp em thông suốt với…!
Đúng vậy, không hẳn cứ nguyên tố là phải chạy sàng; NHƯNG chạy hàng loạt là chuyện khác.
Thuật toán phân tích TSNT đảm bảo những số chia hết đều nguyên tố.
(sửa: h mới đọc kĩ là đang hỏi vụ sàng số, vâng, hỏi như DHV không sàng không hay)
2 Likes
như vậy thì số có nhiều nhất số ước là nguyên tố thì sẽ là số có ước lớn nhất phải không bác…??
Không hẳn. Công thức là: số ước = tích(số mũ của mỗi TSNT + 1) (gọi “vui” là tổng bậc 0, đề bài là bậc 1).
với bài này, em thấy công thức sai bác ạ…!!
Tổng các ước thật sự của 48 bằng:
1 + 2 + 3 + 4 + 6 + 8 + 12 + 16 + 24 = 76
Tìm số có tổng các ước thật sự lớn nhất trong phạm vi từ 1 đến 108.
Công thức nào bạn? Tổng ước thì trừ chính nó ra nữa là đúng.
Thế là phải sàng sao sao…!!
Tại sao vậy ạ…?
Bạn viết:
thì nó là một bài tính hàng loạt => dùng sàng phân đoạn.
1 Like
Ok cám ơn bác…!! 
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?