Уменьшить перебор (поиск числа с наибольшим числом делителей) - Pascal
Формулировка задачи:
Программа для нахождения числа (в промежутке от 1 до m включительно) с наибольшим количеством делителей. В конце выводит само число и количество его делителей.
Здесь практически полный перебор, необходимо уменьшить его количество, чтобы увеличить скорость выполнения программы. Система проверки на 18 примерах из 50 выдает превышение ограничения по времени. Конкретные примеры и ограничения по времени неизвестны. Ограничение для m: 1 <= m <= 100 000. Помогите, пожалуйста, оптимизировать.
var m : longint; max : longint; count : longint; number : longint; i : longint; function getDiv(number: longint): longint; // найти количество делителей var count: longint; i: longint; begin count := 0; for i := 1 to number div 2 do if number mod i = 0 then count := count + 1; getDiv := count + 1; end; begin read(m); max := 0; for i := 1 to m do begin count := getDiv(i); if max < count then begin max := count; number := i; end; end; writeln(number); writeln(max); end.
Решение задачи: «Уменьшить перебор (поиск числа с наибольшим числом делителей)»
textual
Листинг программы
function KolDel(n:integer):integer; var i,k:integer; begin k:=2; //1 и само число for i:=2 to trunc(sqrt(n)) do //остальные делители if n mod i=0 then inc(k,2); if frac(sqrt(n))=0 then dec(k);//если число полный квадрат, то минус 1 result:=k; end;
Объяснение кода листинга программы
- Создается функция с названием
KolDel
, принимающая целочисленный аргументn
и возвращающая целочисленное значение. - Объявляются переменные
i
иk
как целочисленные. - Присваивается переменной
k
значение 2, так как у любого числа 1 и оно само делители. - Запускается цикл с переменной
i
от 2 до целой части квадратного корня из числаn
. - Внутри цикла, если
n
делится наi
без остатка,k
увеличивается на 2. Это связано с тем, что каждый делитель будет обнаружен попарно, например, еслиi
является делителем, тоn/i
также является делителем. - После цикла, если
n
является полным квадратом,k
уменьшается на 1, так как делимое и делитель в этом случае будут одинаковы. - Значение переменной
result
устанавливается равнымk
, и функция завершается.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д