Пусть M(N) — сумма двух наибольших различных натуральных делителей натурального
Найдите 5 наименьших натуральных чисел, превышающих 10 000 000, для которых 0 < M (N) < 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