Число с наибольшим количеством делителей

Число с наибольшим количеством делителей

Все делители числа

Все делители, на которые данное число делится нацело можно получить из разложения числа на простые множители.

Нахождение всех делителей числа выполняется следующим образом:

  1. Сначала нужно разложить данное число на простые множители.
  2. Выписываем каждый полученный простой множитель (без повторов, если какой-то множитель повторяется).
  3. Далее, находим всевозможные произведения всех полученных простых множителей между собой и добавляем их к выписанным простым множителям.
  4. В конце добавляем в качестве делителя единицу.

Например, найдём все делители числа 40. Раскладываем число 40 на простые множители:

Выписываем (без повторов) каждый полученный простой множитель – это 2 и 5.

Далее находим всевозможные произведения всех полученных простых множителей между собой:

2 · 2 = 4
2 · 2 · 2 = 8
2 · 5 = 10
2 · 2 · 5 = 20
2 · 2 · 2 · 5 = 40

Добавляем в качестве делителя 1. В итоге получаем все делители, на которые число 40 делится без остатка:

1, 2, 4, 5, 8, 10, 20, 40

Других делителей у числа 40 нет.

Калькулятор нахождения всех делителей

Данный калькулятор поможет вам получить все делители числа. Просто введите число и нажмите кнопку "Вычислить".

В введенном промежутке натуральных чисел найти те, количество делителей у которых не меньше введенного значения. Для найденных чисел вывести на экран количество делителей и все делители.

Пользователь вводит числовой промежуток — минимальное (a) и максимальное (b) числа. После этого запрашивается искомое количество делителей.

Во внешнем цикле перебираются натуральные числа от a до b. При этом в конце каждой итерации a увеличивается на 1, тем самым приближаясь к b.

В теле внешнего цикла вводится счетчик (m) количества делителей очередного натурального числа. Далее во внутреннем цикле перебираются числа (i) от 1 до a. Если i делит нацело a, то счетчик увеличивается на 1.

Читайте также:  Почему excel не сохраняет файл

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

var
a , b , n , m , i : word ;

begin
write ( ‘Числовой промежуток: ‘ ) ;
readln ( a , b ) ;
write ( ‘Количество делителей не менее. ‘ ) ;
readln ( n ) ;
while a = b do begin
m : = 0 ;
for i : = 1 to a do
if a mod i = 0 then m : = m + 1 ;
if m > = n then begin
write ( a , ‘ — ‘ , m , ‘ — ‘ ) ;
for i : = 1 to a do
if a mod i = 0 then write ( i , ‘ ‘ ) ;
writeln ;
end ;
a : = a + 1 ;
end ;
end .

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

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

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

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

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

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

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

Читайте также:  Почему не запускается ноутбук lenovo

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

n ^ (log2 / log log n)" (ну я примерно передал порядок, на самом деле там формула посложнее)
Дирихле: "СУММА_ d(i) / n

Ссылка на основную публикацию
Adblock detector