Как многие успели убедиться, часто требуется найти количество делителей натурального числа. Предлагаю быстрые алгоритмы для этой задачи.
Код C++
// быстрый алгоритм без использования дополнительной памяти
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++
// быстрый алгоритм с использованием дополнительной памяти
#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++
#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;
}
Код C++
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;
}
Еще один очень быстрый алгоритм нахождения суммы делителей. Отличается от предыдущего меньшим количеством делений. По скорости одинаковы.
Код C++
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;
}