2-19r · informatik.az

Два натуральных числа называются дружественными, если каждое из них равно сумме делителей другого, кроме самого этого числа. Найти все пары дружественных чисел, лежащих в диапазоне от N до M включительно (N < M < 10000)

В этой задаче без функции уже не обойтись. Функция sumdel вычисляет сумму делителей передаваемого ей числа n. Мы учитываем (см. примечание к задаче 2.13), что если число делится на i то оно делится и на n div i (n/i) и оба эти делители прибавляем к сумме – строка 11. А если i является «центром» делителей (i*i=n), то делитель i добавляем к сумме 1 раз – строка 14. В головной программе мы перебираем все пары чисел в диапазоне от n до m и проверяем их при помощи функции sumdel – строка 24, 25.

Program A2_19;

Var

n,m,i,j,d:integer;

Function sumdel(n:integer):integer;

Var s,i:integer;

begin

i:=2; s:=1;

while (i*i<n) do

begin

if (n mod i=0) then s:=s+i+(n div i);

INC(i);

end;

if (i*i=n) then s:=s+i;

sumdel:=s;

end;

begin

readln(n,m);

for i:=n to m-1 do

begin

d:=sumdel(i);

for j:=i+1 to m do

if (j=d) then

if (i=sumdel(j)) then write('(',i,',',j,') ');

end;

writeln;

readln;

end.

// Program A2.19;

#include <iostream>

using namespace std;

int sumdel(int n)

{ int s=1,i;

for (i=2;i*i<n;i++)

if (n%i==0) s=s+i+n/i;

if (i*i==n) s=s+i;

return s;

}

int main()

{ int n,m,i,j,d;

cin>>n>>m;

for (i=n;i<m;i++)

{ d=sumdel(i);

for (j=i+1;j<=m;j++)

if (j==d && i==sumdel(j))

cout<<"("<<i<<","<<j<<") ";

}

cout<<endl;

return 0;

}

Примечание. В программе для поиска пар чисел для проверки, являются ли они дружественными, мы использовали двойной цикл. Во внешнем цикле for i:=n to m-1 do сумма делителей числа i вычисляется 1 раз, а вот во внутреннем цикле for j:=i+1 to m do сумма делителей числа j вычисляется несколько раз. Но существует алгоритм, в котором все пары находятся в одном цикле и время вычисления уменьшается в несколько десятков раз. Найдите этот алгоритм.