Форум программистов, компьютерный форум, киберфорум
Thinker
Войти
Регистрация
Восстановить пароль
Оценить эту запись

Быстрое нахождение суммы делителей натурального числа

Запись от Thinker размещена 10.07.2013 в 09:58
Обновил(-а) Thinker 11.07.2013 в 09:55

Приведу быстрый алгоритм нахождения суммы делителей. Сумма ищется по формуле
https://www.cyberforum.ru/cgi-bin/latex.cgi?S(a) = \frac{p_1^{a_1+1}-1}{p_1-1}\cdot\frac{p_2^{a_2+1}-1}{p_2-1}...\cdot\frac{p_n^{a_n+1}-1}{p_n-1}, где
https://www.cyberforum.ru/cgi-bin/latex.cgi?a=p_1^{a_1}...p_n^{a_n} - каноническое разложение числа a.
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
unsigned long Sum(unsigned long a)
{
   unsigned long sum = 1, k = 1, i;
   if (a == 1)
      return a;
   while ((a & 1) == 0)
   {
      k <<= 1;
      a >>= 1;
   }
   k = (k << 1) - 1;
   if (a == 1)
      return k;
   else
      sum = k;
   for(i = 3; i*i <= a; i += 2)
   {
      k = 1;
      while(a % i == 0)
      {
         k *= i;
         a /= i;
      }
      if (k > 1)
         sum *= ((k * i) - 1)/(i - 1);
   }
   if (a > 1)
      sum *= a + 1;
   return sum;
}

данный алгоритм быстрее обычного цикла от 1 до a в сотни тысяч раз и чем больше число a, тем острее чувствуется разница.
Еще один очень быстрый алгоритм нахождения суммы делителей. Отличается от предыдущего меньшим количеством делений. По скорости одинаковы.
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
unsigned long Sum(unsigned long a)
{
   unsigned long sum = 1, k = 1, i, p;
   if (a == 1)
      return a;
   while ((a & 1) == 0)
   {
      k <<= 1;
      a >>= 1;
   }
   k = (k << 1) - 1;
   if (a == 1)
      return k;
   else
      sum = k;
   for(i = 3; i*i <= a; i += 2)
   {
      p = k = 1;
      while(a % i == 0)
      {
         k *= i;
         p += k;
         a /= i;
      }
      if (k > 1)
         sum *= p;
   }
   if (a > 1)
      sum *= a + 1;
   return sum;
}
Размещено в Без категории
Показов 2071 Комментарии 0
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru