Назовём натуральное число подходящим, если у него ровно 3 различных простых делителя. Например, число 180 подходящее (его простые делители — 2, 3 и 5), а число 12 — нет (у него только два различных простых делителя). Определите количество подходящих чисел, принадлежащих отрезку [50 001; 90 000], а также наименьшее из таких чисел. В ответе запишите два целых числа: сначала количество, затем наименьшее число.
Решим задачу перебором. Приведём решение данной задачи на языке PascalABC:
var del1, del2, count, min, i, j, k: longint;
begin
count := 0;
del1 := 0;
del2 := 0;
min := 90001;
for i := 50001 to 90000 do begin
for j := 2 to i-1 do begin
if i mod j = 0 then begin
for k := 2 to j-1 do begin
if j mod k = 0 then del2 := del2 + 1;
end;
if del2 = 0 then del1 := del1 + 1;
del2 := 0;
end;
end;
if del1 = 3 then begin
count := count + 1;
if min > i then min := i;
end;
del1 := 0;
end;
writeln(count, min);
end.
Результат работы программы — 1558750001.
Ответ: 1558750001.
Приведем другое решение.
Будем раскладывать каждое число из заданного диапазона на простые множители. Единственным четным простым множителем является число 2, поэтому сначала будем делить число на 2 до тех пор, пока результат не окажется нечетным. Затем будем делить на каждое из нечетных чисел до тех пор, пока результат не перестанет делиться на это число. Заметим, что если результат не делится на некоторое число, то он не делится и на все числа, кратные этому числу, поэтому число будет делиться только на простые нечетные числа. Если число хотя бы один раз разделилось на некоторое простое число, то к количеству простых делителей (переменная del) будем прибавлять единицу. Как только количество простых делителей станет больше 3, выходим из цикла.
var del, del1, count, min, i, c, p: longint;
begin
count := 0;
min := 90001;
for i := 50001 to 90000 do begin
c:=i;
del:=0;
del1:=0;
while c mod 2 = 0 do begin
del1:=1;
c:=c div 2;
end;
del:=del+del1;
p:=3;
while c>1 do begin
del1:=0;
while c mod p = 0 do begin
del1:=1;
c:=c div p;
end;
del:=del+del1;
if del>3 then break;
p:=p+2;
end;
if del = 3 then begin
count := count + 1;
if min > i then min := i;
end;
end;
writeln(count, min);
end.