Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [120115; 120200], число, имеющее максимальное количество различных натуральных делителей, если таких чисел несколько — найдите максимальное из них. Выведите на экран количество делителей такого числа и само число.
Например, в диапазоне [80; 90] максимальное количество различных натуральных делителей имеет
12 90
Ответ:
Решим задачу перебором. Будем проверять количество делителей каждого числа из диапазона, если их количество наибольшее — записываем количество делителей и само число в заранее объявленные переменные. После этого выводим эти числа на экран.
Приведём решение на языке Pascal.
var
maxNum, numDel, maxDel, i, j: longint;
begin
maxNum := 0;
maxDel := 0;
for i := 120115 to 120200 do begin
numDel := 0;
for j := 1 to i do begin
if (i mod j = 0) then begin
numDel := numDel + 1;
end;
end;
if (numDel >= maxDel) then begin
maxDel := numDel;
maxNum := i;
end;
end;
writeln(maxDel, ' ', maxNum);
end.
В результате работы программа должна вывести следующее:
128 120120
Приведём другое решение на языке Python.
maxi = 0
for i in range(120115, 120201):
numdel = 0
for j in range(1, i + 1):
if i % j == 0:
numdel += 1
if numdel >= maxi:
maxi = numdel
maxinum = i
print(maxi, maxinum)
Приведём решение Артёма Гридина на языке Python.
def Factorize(n: int) -> list:
ret = []
factor = 2
while factor ** 2 <= n:
if n%factor == 0:
n //= factor
ret.append(factor)
else:
factor += 1
if n != 1:
ret.append(n)
return ret
def CountDivs(n: int) -> int:
factors = Factorize(n)
T = 1
for i in set(factors):
T*= factors.count(i) + 1
return T
d = {}
for i in range(120115, 120201):
d[i] = CountDivs(i)
maxKey, maxValue = 0, 0
for key, value in d.items():
if value > maxValue:
maxValue = value
if key > maxKey:
maxKey = key
print(maxValue, maxKey)