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

Sẵn làm clip luôn

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

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…!

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ớ

Đú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)

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).

Highly composite number

A highly composite number (or anti-prime) is a positive integer with more divisors than any smaller positive integer has. The term was coined by Ramanujan (1915). However, Jean-Pierre Kahane has suggested that the concept might have been known to Plato, who set 5040 as the ideal number of citizens in a city as 5040 has more divisors than any numbers less than it. The related concept of largely composite number refers to a positive integer which has at least as many divisors as any smaller posi...

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.

với bài này, em thấy công thức sai bác ạ…!!

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:

tìm ra số có tổng ước lớn nhất trông khoảng 10^8

thì nó là một bài tính hàng loạt => dùng sàng phân đoạn.

Ok cám ơn bác…!!