|
Два натуральных числа называются дружественными, если каждое из них равно сумме делителей другого, кроме самого этого числа. Найти все пары дружественных чисел, лежащих в диапазоне от 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.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
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 вычисляется несколько раз. Но существует алгоритм, в котором все пары находятся в одном цикле и время вычисления уменьшается в несколько десятков раз. Найдите этот алгоритм.
|
