Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 89, средняя оценка - 4.89
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
28.09.2012, 19:47     Быстрое нахождение количества делителей натурального числа #1
Как многие успели убедиться, часто требуется найти количество делителей натурального числа. Предлагаю быстрые алгоритмы для этой задачи.

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;
}
Предлагаю всем желающим попробовать свои силы и написать что-то быстрее представленного выше.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.09.2012, 19:47     Быстрое нахождение количества делителей натурального числа
Посмотрите здесь:

Сумма делителей данного натурального числа C++
C++ Нахождение наименьшего нечетного натурального делителя k (k≠1) любого заданного натурального числа n
Функция - число делителей натурального числа C++
Найти сумму делителей натурального числа C++
Нахождение количества делителей числа через рекурсию C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
yekka
384 / 148 / 8
Регистрация: 12.05.2011
Сообщений: 450
28.09.2012, 21:58     Быстрое нахождение количества делителей натурального числа #2
Цитата Сообщение от Thinker Посмотреть сообщение
#define N 100
N -- это количество простых чисел в нижеследующем массиве что ли?
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
28.09.2012, 22:12  [ТС]     Быстрое нахождение количества делителей натурального числа #3
Цитата Сообщение от yekka Посмотреть сообщение
N -- это количество простых чисел в нижеследующем массиве что ли?
да, именно. массив можно и из тысячи элементов использовать. Это для того, чтобы не писать вычисление sizeof(prime)/sizeof(*prime). Тут уже различные вариации возможны. Главное - алгоритм.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
09.10.2012, 20:10  [ТС]     Быстрое нахождение количества делителей натурального числа #4
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Дополню сюда очень быстрый алгоритм нахождения суммы делителей
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, тем острее чувствуется разница.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
11.10.2012, 13:54  [ТС]     Быстрое нахождение количества делителей натурального числа #5
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Еще один очень быстрый алгоритм нахождения суммы делителей. Отличается от предыдущего меньшим количеством делений. По скорости одинаковы.
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;
}
Pepsy
47 / 32 / 4
Регистрация: 05.01.2013
Сообщений: 307
13.01.2013, 21:11     Быстрое нахождение количества делителей натурального числа #6
Вот такой вопрос: а как вы определяете скорость? не на секундомере же.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
13.01.2013, 21:37     Быстрое нахождение количества делителей натурального числа #7
Цитата Сообщение от Pepsy Посмотреть сообщение
не на секундомере же.
Можно и на секундомере. Но вообще, есть такая вещь как ассимптотическая сложность. В исходниках выше она равна O(sqrt(n)).
Можно ее ускорить, если взять более эффективный алгоритм факторизации(метод квадратичного решета, например).
shalad
 Аватар для shalad
7 / 7 / 0
Регистрация: 17.05.2010
Сообщений: 122
26.02.2013, 15:18     Быстрое нахождение количества делителей натурального числа #8
Thinker, Не подскажете, есть ли название у третьего алгоритма в Вашем первом посте? Хотелось бы его разобрать, но пока что для меня все, что происходит внутри - магия
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
11.06.2013, 09:50  [ТС]     Быстрое нахождение количества делителей натурального числа #9
Цитата Сообщение от shalad Посмотреть сообщение
Thinker, Не подскажете, есть ли название у третьего алгоритма в Вашем первом посте?
Пока я его никак не назвал, просто придумал diagon предлагает еще оптимизировать.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.02.2016, 13:26     Быстрое нахождение количества делителей натурального числа
Еще ссылки по теме:

Определить К - количество делителей натурального числа N C++
C++ Вычисление суммы делителей натурального числа
C++ Быстрое нахождение максимального делителя числа

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
_Murchik_
0 / 0 / 0
Регистрация: 11.10.2015
Сообщений: 5
06.02.2016, 13:26     Быстрое нахождение количества делителей натурального числа #10
Thinker, а можно найти четное или не четное количество делителей, ваш алгоритм не проходит по времени
Миниатюры
Быстрое нахождение количества делителей натурального числа   Быстрое нахождение количества делителей натурального числа  
Yandex
Объявления
06.02.2016, 13:26     Быстрое нахождение количества делителей натурального числа
Ответ Создать тему
Опции темы

Текущее время: 21:46. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru