Форум программистов, компьютерный форум, киберфорум
Thinker
Войти
Регистрация
Восстановить пароль
Рейтинг: 5.00. Голосов: 1.

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

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

Часто требуется найти количество делителей натурального числа и, по возможности, это надо осуществить очень быстро. В следующем быстром алгоритме количество делителей ищется по формуле
https://www.cyberforum.ru/cgi-bin/latex.cgi?count(a) = (a_1+1)(a_2+1)...(a_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
// быстрый алгоритм без использования дополнительной памяти
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;
}
Размещено в Без категории
Показов 2023 Комментарии 0
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru