Часто в олимпиадных задачах, чтобы оценить асимптотику алгоритма, требуется знать примерное число делителей поступающего на вход числа. Точнее, требуется знать максимальное число делителей среди всех чисел до, скажем, миллиарда.

Самая грубая оценка - O (sqrt(N)), а именно, не более двух квадратных корней из N.

Но часто это оказывается слишком грубой оценкой, неоправданно завышенной.

Обычная используемая мной оценка - O(кубического корня из N). Эту таинственную оценку я услышал когда-то давно от кого-то, и никогда её не понимал, но пользовался ей, и она работала.

Совсем недавно мы делали стресс-тест, и на числах до миллиарда она подтвердилась - число делителей не превосходит двух кубических корней из числа. Этого "доказательства" вполне достаточно, чтобы и дальше применять эту оценку на практике. Но найти ей математическое объяснение ну никак не получалось.

Сегодня в очередной раз решил поискать на эту тему в интернете. На этот раз нашёл то. что нужно, на удивление быстро: en.wikipedia.org/wiki/Divisor_function. Здесь много всякого интересного, но вот главная вещь, поразительная для меня формула:

"для любого eps>0 выполняется: d(n) = o(n^eps)"

Выходит, на самом деле число делителей ведёт себя на бесконечности не только лучше квадратного, кубического и прочего корней из числа n; оно вообще является субполиномиальной величиной!

Другие оценки:

• Wigert:  "d(n)  ~  n ^ (log2 / log log n)"  (ну я примерно передал порядок, на самом деле там формула посложнее)
• Дирихле:  "СУММА_{i=1..n} d(i) / n  ~  log n + 2 gamma - 1"

P.S. Некоторым это может показаться бояном, но я знаю, что многие до сих пор даже не знают, что число делителей меньше квадратного корня, не говоря уже о таких "крутых" оценках :)

P.P.S. Для олимпиад, где обычно в таких задачах мы имеем дело с числами до 10^9 - 10^12, эти оценки малополезны (здесь надо по-прежнему брать корень кубический), но они интересны чисто как математический факт.