Нахождение всех делителей числа

[frankenstein]

Недавно встала такая задача:
Дано некое положительное число, надо найти все его делители, кроме его самого.
Задача в том чтобы написать как можно более быстрый алгоритм, и конечно же
корректный.
Первая идея была, перебирать меньшие числа, проверяя на делимость, но полный
перебор не дал широких пределов применения, уже для решения задачи например для
$2^{32}$, этот алгоритм работал очень долго, после нескольких модификаций
я получил вот такой вот алгоритм, верхняя оценка сложности в худшем случае $O(\sqrt{n})$.
Алгоритм заполняет вектор детелями числа.

void find_divs( int n, vector<int> & divs ) {
   int d, dlim, m = 1;
   divs.push_back(1);

   dlim = sqrt( n );
   for ( d = 2; d <= dlim; ++d ) {
      if ( n%d == 0 ) {
         divs.push_back(m*d);
         if ( m*d != n/d )
            divs.push_back(n/d);
         n /= d;
         m *= d;
         dlim = sqrt( n );
      }
   }
}

Можно ли как-то улучшить алгоритм? Или есть более быстрые методы решения этой задачи?

[venco]

frankenstein в сообщении #883340 писал(а):

Можно ли как-то улучшить алгоритм?

Для начала надо бы его исправить. Проверьте, что у вас получится для 12 и 36.

frankenstein в сообщении #883340 писал(а):

Или есть более быстрые методы решения этой задачи?

Сначала получите разложение входного числа на простые множители. Дальше перебираете все комбинации простых множителей.

[frankenstein]

Цитата:

Для начала надо бы его исправить. Проверьте, что у вас получится для 12 и 36.

Да, алгоритм работает неправильно ). Думаю эта правильная:

void find_divs( int n, vector<int> & divs ) {
   int d, dlim, m = 1;
   divs.push_back(1);

   dlim = sqrt( n );
   for ( d = 2; d <= dlim; ++d ) {
      if ( n%d == 0 ) {
         divs.push_back(m*d);
         if ( m*d != n/d )
            divs.push_back(n/d);
         n /= d;
         m *= d;
         dlim = sqrt( n );
      }
   }
}

Цитата:

Сначала получите разложение входного числа на простые множители. Дальше перебираете все комбинации простых множителей.

Да, была такая идея, на перебор комбинаций уйдет где-то $2^{number of prime factors of n}$ итераций, как в этом случае оценить сложность алгоритма? Есть ли какая нибудь формула для вычисления количества простых множителей числа. Или хотя бы надо оценить верхнюю границу, т.е. найти число, которое разлагается на максимальное число простых множителей.

[venco]

frankenstein в сообщении #883346 писал(а):

Думаю эта правильная:

Надеюсь вы проверили хотя бы на 12 и 36?

Сложность алгоритма, как минимум - собственно число делителей, а перебор по простым делителям даст именно такую сложность (без учёта факторизации). Естественно, не надо хранить и перебирать каждую двойку отдельно - нужно лишь их количество.

[Батороев]

Может, поможет следующее:

Если $n= x^ay^b... $

то все делители можно определить из выражения: $(x^a+x^{a-1}+...+1)(y^b+y^{b-1}+...+1)...$

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

[frankenstein]

Хотелось быстрее результата как программу, которая может сделать это за позволительное время и вот она:

void get_div(int n, vector<int> & divs) {
 int d, dlim;
 dlim = sqrt( n );
 for (d = 2; d <= dlim; ++d) {
  if (n%d == 0) {
   divs.push_back(d);
    if ( d != n/d )
     divs.push_back(n/d);
  }
 }
}