Тип 25 № 47022 
Обработка целочисленной информации. Нахождение делителей
i
Пусть M (N) — пятый по величине делитель натурального числа N без учёта самого числа и единицы. Например, M(1000) = 100.
Если у числа N меньше 5 различных делителей, не считая единицы и самого числа, считаем, что M (N) = 0.
Найдите 5 наименьших натуральных чисел, превышающих 300 000 000, для которых M (N) > 0. В ответе запишите найденные значения M (N) в порядке возрастания соответствующих им чисел N.
Примечание.
Пятый по величине делитель — пятый делитель из пяти наибольших делителей числа. То есть для числа 1000 пять наибольших делителей, не считая единицы и самого числа, — 500, 250, 200, 125, 100, пятый по величине — 100.
Решение. Будем последовательно рассматривать каждое целое число, большее 300 000 000. В каждом таком числе будем находить наименьшие шесть натуральных делителей. Если у числа есть по крайней мере пять делителей, не считая единицы и самого числа, будем выводить результат деления числа на пятый найденный делитель.
Приведём решение на языке Pascal.
var
i, j, halfI, del: int64;
countDel, count: integer;
begin
count := 0;
i := 300000001;
while (count < 5) do begin
halfI := i div 2;
del := 0;
countDel := 0;
for j := 2 to halfI do
if (i mod j = 0) then begin
countDel := countDel + 1;
if countDel = 5 then begin
writeln(i div j);
count := count + 1;
break;
end;
end;
i := i + 1;
end;
end.
В результате работы программа должна вывести следующее:
17
1119403
151
16666667
27272728
Приведём решение на языке Python.
count = 0
i = 300000001
while count < 5:
halfI = i // 2
countDel = 0
for j in range(2, halfI + 1):
if i % j == 0:
countDel += 1
if countDel == 5:
print(i // j)
count += 1
break
i += 1
Приведём другое решение Замахова Егора на языке Python.
import math
k = 300000001
c = 0
while True:
s = []
for i in range(math.ceil(k ** 0.5) + 1, 1, -1):
if k % i == 0:
s.append(i)
s.append(k / i)
if len(s) >= 5:
print(int(sorted(s)[-5]))
c += 1
if c == 5:
break
k += 1
Ответ: 17&1119403&151&16666667&27272728
47022
17 1119403 151 16666667 27272728
PDF-версии: