Даны два целых положительных числа M, N. Требуется найти все «дружественные» пары чисел на отрезке [M; N]. Дружественным для числа А является такое число В, что оно равно сумме делителей А, исключая само значение А. И наоборот, сумма делителей В, исключая В, равняется А. A не равно B.
Input
Со стандартного устройства ввода в первой строке через пробел вводятся два целых
положительных числа M (2<=M<=105 ) и N (2<=M<=N<=105 ).
Output
Требуется вывести все пары «дружественных» чисел, расположенные на отрезке [M; N].
Пару «дружественных» чисел (E, F) нужно выводить раньше пары «дружественных»
чисел (K, P), когда минимальный элемент пары «дружественных» чисел (E, F) меньше
минимального элемента пары «дружественных» чисел (K, P).
Число E в паре «дружественных» чисел (E, F) нужно выводить раньше числа F из этой
же пары, когда Е меньше F.
Числа в паре нужно разделять пробелом, ставить пробел после второго члена пары
не нужно.
Sample Input
210 294
Sample Output
220 284
Примечание
Попробуйте реализовать функцию getSumOfDivisors(n), которая принимает число n, а
возвращает сумму делителей числа n, кроме самого n.
Мой код
#include <stdio.h>
#include <math.h>
int getSumOfDivirsors(int a)
{
int i,p;
p = 1;
for (i = 2; i <= a / 2; i++)
if (a % i == 0) p = p + i;
return p;
}
int main()
{
int m, n, e, f, i, tr1, tr2;
scanf("%d%d", &m, &n);
if (m < 220) m = 220;
if (n > 88730) n = 88730;
for (i = m; i < n; i++)
{
tr1 = getSumOfDivirsors(i);
if (tr1 <= n) {
tr2 = getSumOfDivirsors(tr1);
if (i == tr2 && tr1!=tr2) { printf("%d %d", tr2, tr1); printf("\n"); i = tr1; }
}
}
}
Выходит за временные рамки в 1с. Как можно улучшить код, чтобы укладывался в 1с ?
for (i = 2; i <= a / 2; i++) ;