Назовём натуральное число подходящим, если у него больше 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.