Приведу быстрый алгоритм нахождения суммы делителей. Сумма ищется по формуле
 , где
 - каноническое разложение числа 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;
} |
|
|
