Назовём нетривиальным делителем натурального числа его делитель, не равный единице и самому числу. Например,
Например, в диапазоне [5; 16] ровно три различных натуральных делителя имеет
16 8
Ответ:
Если решать задачу перебором — программа будет существенно неэффективна по времени. Заметим, что у каждого делителя числа имеется пара, например, пары делителей
Приведём решение на языке Pascal.
var
numDel, i, j: longint;
maxDel: longint;
sqrtI: real;
begin
for i := 289123456 to 389123456 do begin
sqrtI := sqrt(i);
numDel := 0;
if (round(sqrtI) = sqrtI) then begin
maxDel := 1;
for j := 1 to round(sqrtI) do
if (i mod j = 0) then begin
if (maxDel = 1) and (j <> 1) then maxDel := i div j;
if (j <> round(sqrtI)) then numDel := numDel + 2;
if (j * j = i) then numDel := numDel + 1;
end;
if numDel = 5 then writeln(i, ' ', maxDel);
end;
end;
end.
В результате работы программа должна вывести следующее:
294499921 2248091
352275361 2571353
373301041 2685619
Приведём другое решение.
Заметим, что ровно три нетривиальных делителя имеет число, из которого можно извлечь корень четвёртой степени, причём получившееся при этом число обязательно должно быть простым.
Приведём решение на языке Pascal.
var
i, del: integer;
control: boolean;
begin
del := 2;
i := round(power(289123456, 0.25));
while (power(i, 4) <= 389123456) do begin
while (i mod del <> 0) do begin
del := del + 1;
if (i < 3) or (del = i) then control := True
else control := False;
end;
if control then writeln(power(i, 4), ' ', power(i, 3));
i := i + 1;
del := 2;
control := False;
end;
end.
В результате работы программа должна вывести следующее:
294499921 2248091
352275361 2571353
373301041 2685619
Приведём другое решение на языке Python.
for i in range(289123456, 389123457):
sqrti = i**0.5
numdel = 0
if round(sqrti) == sqrti:
maxdel = 1
for j in range(2, round(sqrti) - 1):
if i % j == 0:
if maxdel == 1: maxdel = i // j
numdel += 2
if numdel == 2: print(i, maxdel)
Приведём решение Станислава Степанова на языке Python.
for i in range(int(289_123_456 ** 0.25), int(389_123_456 ** 0.25)):
for j in range(2, i):
if not i % j: # Проверка на простое число
break
else:
print(i ** 4, i ** 3)
Приведём решение Бориса Савельева на языке Python.
for i in range(17004, 19726 + 1):
a = []
x=i*i
for j in range(2, i + 1):
if x % j == 0:
a.append(j)
if j != (x // j):
a.append(x // j)
if len(a) > 3:
break
if len(a) == 3:
print(x, max(a))