Уменьшить перебор (поиск числа с наибольшим числом делителей) - Pascal

Узнай цену своей работы

Формулировка задачи:

Программа для нахождения числа (в промежутке от 1 до m включительно) с наибольшим количеством делителей. В конце выводит само число и количество его делителей.
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.
Здесь практически полный перебор, необходимо уменьшить его количество, чтобы увеличить скорость выполнения программы. Система проверки на 18 примерах из 50 выдает превышение ограничения по времени. Конкретные примеры и ограничения по времени неизвестны. Ограничение для m: 1 <= m <= 100 000. Помогите, пожалуйста, оптимизировать.

Решение задачи: «Уменьшить перебор (поиск числа с наибольшим числом делителей)»

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;

Объяснение кода листинга программы

  1. Создается функция с названием KolDel, принимающая целочисленный аргумент n и возвращающая целочисленное значение.
  2. Объявляются переменные i и k как целочисленные.
  3. Присваивается переменной k значение 2, так как у любого числа 1 и оно само делители.
  4. Запускается цикл с переменной i от 2 до целой части квадратного корня из числа n.
  5. Внутри цикла, если n делится на i без остатка, k увеличивается на 2. Это связано с тем, что каждый делитель будет обнаружен попарно, например, если i является делителем, то n/i также является делителем.
  6. После цикла, если n является полным квадратом, k уменьшается на 1, так как делимое и делитель в этом случае будут одинаковы.
  7. Значение переменной result устанавливается равным k, и функция завершается.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

15   голосов , оценка 4.067 из 5
Похожие ответы