РЕШУ ЕГЭ — информатика

Задания

Назовём натуральное число подходящим, если у него больше 17 различных делителей (включая единицу и само число). Определите количество подходящих чисел, принадлежащих отрезку [30 001; 70 000], а также наименьшее из таких чисел. В ответе запишите два целых числа: сначала количество, затем наименьшее число.

Решение. Решим задачу перебором. Приведём решение данной задачи на языке Паскаль:

var del, count, min, i, j: longint;
begin
  count := 0;
  del := 0;
  min := 50001;
  for i := 30001 to 70000 do begin
      for j := 1 to i do begin
          if i mod j = 0 then del := del + 1;
      end;
      if del > 17 then begin
          count := count + 1;
          if min > i then min := i;
      end;
      del := 0;
  end;
  writeln(count, min);
end.

Результат работы программы  — 706630008.

Заметим, что время работы программы можно существенно уменьшить, если осуществлять перебор делителей не до самого числа, а до квадратного корня из числа. Тогда, если число i делится на число j, то к количеству делителей del надо прибавлять 2: для делителя j и делителя i/j. Кроме того, если число j является квадратным корнем из числа i, то делители j и i/j совпадают, поэтому количество делителей del надо уменьшить на единицу. Приводим программу на языке Pascal, реализующую этот способ:

var del, count, min, i, j, sqrtI: longint;
begin
  count := 0;
  min := 50001;
  for i := 30001 to 70000 do begin
      del := 0;
      sqrtI := round(sqrt(I));
      for j := 1 to sqrtI do begin
          if i mod j = 0 then del := del + 2;
      end;
      if sqrtI*sqrtI = i then del := del - 1;
      if del > 17 then begin
          count := count + 1;
          if min > i then min := i;
      end;
  end;
  writeln(count, min);
end.

Результат работы программы  — 706630008.

Ответ: 706630008.

№ п/п	№ задания	Ответ
1	33762	706630008

Ключ