Написать поиск всех дружественных чисел в заданном диапазоне. Оптимизация - C (СИ)

Формулировка задачи:

Необходимо написать поиск всех дружественных чисел в диапазоне 2..1е6. Я смог решить задачу только "в лоб" - простой перебор, который считает ооочень долго по понятным причинам.

#include <stdio.h>
#include <conio.h>
#include <math.h>
 
int main()
{
    int n1, n2, d1, d2, i, h;
    for(h=2; h<1e6; h++)
      {
             n1=h;
             d1=1;
             d2=1;
             for(i=2; i<=sqrt(n1); i++)
               if(n1%i==0)
                 d1+=i;
                 
             n2=d1;
             for(i=2; i<=sqrt(n2); i++)
               if(n2%i==0)
                 d2+=i;
                 
             if(n1==d2&&n1<n2&&n1!=n2)
               printf("%d %d\n", n1, n2);
               }
               
      getch();
}

Попробовал заменить условие выхода из проверки путем i<=sqrt(n1), но почему-то не выходит. Подскажите, что не так и что здесь можно улучшить. Заранее спасибо.

Решение задачи: «Написать поиск всех дружественных чисел в заданном диапазоне. Оптимизация»

Листинг программы

#include <stdio.h>
#define N 1000001
 
main() {
  int i, n, d, s;
  static int fr[N];
  for (n=2; n < N; n++) {
    for (i= 2, s= 1; i <= (d= n / i); i++) if (!(n%i)) {
      if (d == i) s+= i;
      else s+= i + d;
      if (s >= N) { s=0; break; }
    }
    fr[n]= s;
  }
  for (n= 1; n < N; n++) if (fr[fr[n]] == n) {
    printf ("%d %d\n", n, fr[n]);
    fr[fr[n]]= 0;
  }
}

Объяснение кода листинга программы

В этом коде ищется все дружественные числа в заданном диапазоне.

Создается массив fr размером N, который инициализируется единицами.
В цикле main() для каждого числа n (начиная с 2 и до N-1) ищутся все делители d этого числа в диапазоне от 2 до квадратного корня из n.
Если число n делится на i без остатка, то к сумме s прибавляется i, если d равно i, и i+d, если d больше i.
Если сумма s превышает N, то она обнуляется и цикл прерывается.
В конце программы выводятся все пары чисел n и fr[n], где n является дружественным числом. Обратите внимание, что в этом коде не проверяется, является ли число n дружественным для самого себя.