Часто требуется найти количество делителей натурального числа и, по возможности, это надо осуществить очень быстро. В следующем быстром алгоритме количество делителей ищется по формуле
 , где
 - каноническое разложение числа 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
| // быстрый алгоритм без использования дополнительной памяти
unsigned long Count(unsigned long a)
{
unsigned long count = 1, k = 0, i;
if (a == 1 || a == 2)
return a;
while ((a & 1) == 0)
{
k++;
a >>= 1;
}
if (a == 1)
return k + 1;
else
count = k + 1;
for(i = 3; i*i <= a; i += 2)
{
k = 0;
while(a % i == 0)
{
k++;
a /= i;
}
count *= (k + 1);
}
if (a > 1)
count <<= 1;
return count;
} |
|
Если имеется возможность выделения дополнительной памяти, то можно ускорить предыдущий алгоритм за счет введения массива простых чисел. В алгоритме ниже размер массива prime не зависит от функции Count (и наоборот), поэтому данный массив можно расширить. Чем больше в нем элементов при большом тестируемом числе, тем лучше
Кликните здесь для просмотра всего текста
| 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
32
33
34
35
36
37
38
39
| // быстрый алгоритм с использованием дополнительной памяти
#define N 100
unsigned long prime[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541};
unsigned long Count(unsigned long a)
{
unsigned long count1 = 1, count2 = 1, k, i;
if (a == 1 || a == 2)
return a;
for(i = 0; i < N && prime[i]*prime[i] <= a; i++)
{
k = 0;
while(a % prime[i] == 0)
{
k++;
a /= prime[i];
}
count1 *= (k + 1);
}
if (a == 1)
return count1;
if (i < N)
return count1 << 1;
for(i = prime[N - 1] + 2; i*i <= a; i += 2)
{
k = 0;
while(a % i == 0)
{
k++;
a /= i;
}
count2 *= (k + 1);
}
if (a > 1)
count2 <<= 1;
return count1 * count2;
} |
|
Если отдельно двойку сдвигами обработать, то небольшой прирост производительности для больших чисел получается по сравнению с предыдущим алгоритмом:
Кликните здесь для просмотра всего текста
| 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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| #define N 100
unsigned long prime[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541};
unsigned long Count(unsigned long a)
{
unsigned long count1 = 1, count2 = 1, k = 0, i;
if (a == 1 || a == 2)
return a;
while ((a & 1) == 0)
{
k++;
a >>= 1;
}
if (a == 1)
return k + 1;
else
count1 = k + 1;
for(i = 0; i < N && prime[i]*prime[i] <= a; i++)
{
k = 0;
while(a % prime[i] == 0)
{
k++;
a /= prime[i];
}
count1 *= (k + 1);
}
if (a == 1)
return count1;
if (i < N)
return count1 << 1;
for(i = prime[N - 1] + 2; i*i <= a; i += 2)
{
k = 0;
while(a % i == 0)
{
k++;
a /= i;
}
count2 *= (k + 1);
}
if (a > 1)
count2 <<= 1;
return count1 * count2;
} |
|
|
