Hosted by uCoz

Задача № 21. Проверить, являются ли два натуральных числа дружественными

Формулировка. Даны два натуральных числа. Проверить, являются ли они дружественными.

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

Например, 220 и 284 – пара дружественных чисел, потому что:

Сумма собственных делителей 220: 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284

Сумма собственных делителей 284: 1 + 2 + 4 + 71 + 142 = 220

Решение. Эта задача напоминает задачу 20, так как в ней мы тоже считали сумму собственных делителей введенного числа, а затем сравнивали эту сумму с самим числом, проверяя его на предмет совершенности. В данном же случае нам нужно найти не только сумму собственных делителей первого числа (обозначим число как n1, а сумму его делителей sum1), но и второго числа (возьмем обозначения n2 и sum2 соответственно). Тогда ответом в задаче послужит сравнение: (n1 = sum2) and (n2 = sum1). Кстати, здесь впервые в нашем повествовании мы используем логические операции (напомним, что логическое выражение X1 and X2 принимает значение истины тогда и только тогда, когда истинны булевские выражения X1 и X2, а в остальных случаях оно принимает ложное значение).

Однако предложенную схему можно упростить. Покажем это на примере: пусть даны числа 8 и 4. Считаем сумму собственных делителей числа 8: 1 + 2 + 4 = 7. Это число отлично от 4, поэтому пара уже не соответствует определению дружественных чисел. Можно сразу вывести отрицательный ответ, избежав подсчета суммы делителей второго числа. Если были бы даны числа 8 и 7, то необходимо было бы вычислить сумму собственных делителей числа 7, она равна 1 (так как оно простое). Теперь необходимо сравнить сумму собственных делителей второго с первым числом: так как 1 отлично от 8, числа не дружественные.

Покажем на блок-схеме, как можно разветвить программу (вычисление обоих сумм не изображается):

Таким образом, без логических операций можно и обойтись.

Код:

  1. program AmicableTest;
  2. var
  3. i, n1, n2, sum1, sum2: word;
  4. begin
  5. readln(n1, n2);
  6. for i := 1 to n1 div 2 do begin
  7. if n1 mod i = 0 then sum1 := sum1 + i
  8. end;
  9. if sum1 = n2 then begin
  10. for i := 1 to n2 div 2 do begin
  11. if n2 mod i = 0 then sum2 := sum2 + i
  12. end;
  13. writeln(sum2 = n1)
  14. end
  15. else begin
  16. writeln('False')
  17. end
  18. end.