Дружественные числа

Дружественными числами называются два различных натуральных числа, для которых сумма всех собственных делителей первого числа (сумма всех делителей, отличных от самого числа) равна второму числу и сумма всех собственных делителей второго числа равна первому числу.

Примеры дружественных чисел: 220 и 284. Делители числа 220: 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 (в сумме дают число 284); делители числа 284: 1, 2, 4, 71, 142 (в сумме 220).
Примеры других пар дружественных чисел: 2620 и 2924, 17296 и 18416.

Написать программу, которая по заданному натуральному числу N находит все пары дружественных чисел, не превосходящих N.

Вот. Кажется, так.

  1. program Fr;
  2. var t,i,n:integer;
  3. function sum_del (n:integer):integer;
  4. var l,sum:word;
  5. begin
  6.  sum:=1;
  7.  for l:=2 to (n-1) do begin
  8.   if (n mod l)=0 then begin inc(sum,l)
  9.  end;
  10.  sum_del:=sum
  11.  end
  12. end;
  13. BEGIN
  14.  readln(n);
  15.  for i:=1 to n do begin
  16.   t:=sum_del(i);
  17.   if ((sum_del(t)=i) and (t>i) and (t<=n)) then writeln (i,' ',t)
  18.  end;
  19.  readln
  20. END.

Да, программа находит такие

Да, программа находит такие числа, но работает весьма медленно.
Первое, что стоило бы сделать - это отказаться от типа Word внутри функции в пользу типа Integer, т.к. тип Word ограничивает область применения только до 65535.
Оптимизировать по скорости можно за счет сокращения числа шагов в цикле подсчета суммы делителей. Для нахождения суммы делителей числа достаточно Sqrt (n) шагов.
Что реально может дать оптимизация. Ваш вариант для n = 100000 отработал у меня за 27 секунд. Оптимизированный вариант решения для того же n отработал за 0.1 секунды.
Попробуйте улучшить код.

    program Fr;     var

  1.     program Fr;
  2.     var t,i,num,n:longint;
  3.     function sum_del (n:longint):longint;
  4.     var D,l,sum:longint;
  5.     begin
  6.      sum:=1;
  7.      for l:=2 to trunc(sqrt(n)) do begin
  8.       if (n mod l)=0 then begin inc(sum,l);
  9.       D:=n div l;
  10.       if (D<>l) then inc(sum,D)
  11.      end;
  12.      sum_del:=sum
  13.      end
  14.     end;
  15.     BEGIN
  16.      readln(n);
  17.      num:=1;
  18.      for i:=1 to n do begin
  19.       t:=sum_del(i);
  20.       if ((sum_del(t)=i) and (t>i)) then begin
  21.        writeln (num,') ',i,' ',t);
  22.        inc(num)
  23.       end
  24.      end;
  25.      readln
  26.     END.

Молодец, схватываешь на лету

Молодец, схватываешь на лету :)

Некоторые замечания по решению:

1. Если компилировать программу в Делфи, то тип LongInt соответствует типу Integer, потому можно было везде использовать тип Integer. Но это даже не замечание, а просто информация. Подробнее о целочисленных типах данных тут: http://it-starter.ru/content/tselochislennye-tipy-dannykh-v-yazyke-pascal

2. Программа выдает лишние пары чисел. Например, для n = 1000000 должно получиться 40 пар, а у тебя их 42:
41) 947835 1125765
42) 998104 1043096
По условию числа не должны превосходить заданное n.

3. Есть возможность еще немного ускорить программу (где-то в 2 раза) за счет следующего:
3.1. Достаточно изменить порядок следования условий в if на такой:
if (t>i) and (t <= n) and (sum_del(t)=i) then (жирным я выделил дополнительное условие для контроля выхода за пределы n)
как программа для n = 1000000 отрабатывает уже не за 4 секунды (что происходит в твоем варианту), а за 2.7 секунды.
Почему так происходит? Дело в том, что при проверке истинности подобного условия, когда у нас используется and, если первая часть (t > i) оказывается ложной, то дальнейшие части условия не проверяются, т.е. не будет и вызываться функция sum_del(t), которая в нашей задачи самая медленная часть.
3.2. Можно еще при подсчете суммы проверять, не превосходит ли сумма заданного предела, если превосходит, то прерывать цикл подсчета суммы. Такая оптимизация даст порядка 10% ускорения, потому можно ее и опустить.

Вообще, повторюсь, я доволен твоим решением.

Спасибо :) Ну, программу

Спасибо :)
Ну, программу делал в Turbo Pascal. Поэтому longint. Кстати, каким образом в TP можно замерить время работы программы? Есть какая-нибудь стандартная функция?

В Делфи функция GetTickCount

В Делфи функция GetTickCount возвращает время в миллисекундах с момента запуска ОС. На счет Turbo Pascal ничего посоветовать не могу.