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