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

@Antimorkovka · Регистрация: 18.12.2013

Author24 — интернет-сервис помощи студентам

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

C

#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), но почему-то не выходит.
Подскажите, что не так и что здесь можно улучшить.
Заранее спасибо.

@NoMasters · 27.01.2014, 22:14

Для поиска суммы делителей можно воспользоваться этим, будет весьма быстро.

@gng · 27.01.2014, 23:16

Тупым перебором справляется за 15 секунд. Но если миллион может превратиться в миллиард, то не обойтись без алгоритмов по ссылке NoMasters
Код ниже включает также поиск совершенных чисел, таких как 6. Если не нужно, исправьте.

C

#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;
  }
}

@NoMasters Псевдослучайный 1946 / 1145 / 98 Регистрация: 13.09.2011 Сообщений: 3,215
	27.01.2014, 22:14	2
	Для поиска суммы делителей можно воспользоваться этим, будет весьма быстро. 1

	27.01.2014, 23:16