Тип 25 № 40741 
Обработка целочисленной информации. Нахождение делителей
i
Пусть M(N) — сумма двух наибольших различных натуральных делителей натурального числа N, не считая самого числа. Если у числа N меньше двух таких делителей, то M (N) считается равным 0.
Найдите 5 наименьших натуральных чисел, превышающих 10 000 000, для которых 0 < M (N) < 10 000. В ответе запишите найденные значения M (N) в порядке возрастания соответствующих им чисел N.
Решение. Будем последовательно рассматривать каждое целое число, большее 10 000 000. В каждом таком числе будем находить наибольшие 2 натуральных делителя, складывая их. Если сумма первых двух наибольших натуральных делителей числа будет меньше 10 000, будем выводить эту сумму на экран.
Приведём решение на языке Pascal.
var
i, j, halfI, del: int64;
countDel, count: integer;
begin
count := 0;
i := 10000001;
while (count < 5) do begin
halfI := i div 2;
del := 0;
countDel := 0;
for j := halfI downto 2 do
if (i mod j = 0) then begin
countDel := countDel + 1;
del := del + j;
if del > 10000 then break
else if countDel = 2 then begin
writeln(del);
count := count + 1;
break;
end;
end;
i := i + 1;
end;
end.
В результате работы программа должна вывести следующее:
6876
6374
6924
8024
8358
Приведём решение на языке Python.
count = 0
i = 10000001
while count < 5:
halfI = i // 2
dell = 0
countDel = 0
for j in range(halfI, 1, -1):
if i % j == 0:
countDel += 1
dell += j
if dell > 10000:
break
elif countDel == 2:
print(dell)
count += 1
break
i += 1
Приведём решение Юрия Красильникова на языке Python эффективное по времени выполнения.
def delit(n):
d = []
k = 2 # или 1 для задач, где требуются делители 1 и n
while k**2 <= n:
if n%k == 0:
d.append(k)
if n//k != k:
d.append(n//k)
k += 1
return d
def m(n):
d=delit(n)
if len(d) < 2:
return 0
else:
d.sort()
return d[-1] + d[-2]
k = 0
n = 10000001
while k<5:
mn = m(n)
if 0 < mn < 10000:
k += 1
print(mn)
n += 1
Приведём решение Бориса Савельева на языке Python.
cnt=1
for i in range (10**7+1,10**18+1):
k=int(i**0.5)
a=[]
for j in range (2,k+1):
if i % j==0:
a.append(j)
if j!=(i//j):
a.append(i//j)
if len(a)>=2:
a.sort()
if (a[-1]+a[-2])<10000:
print(a[-1]+a[-2])
cnt+=1
if cnt==6:
break
Ответ: 6876&6374&6924&8024&8358
40741
6876 6374 6924 8024 8358
PDF-версии: